Many organisms avoid previously exploited patches to increase their foraging efficiency. Such avoidance behavior either requires systematic search, memorizing which patches have been visited, the deposition of a cue or signal that marks exploited patches, or a combination of these abilities. Usually we ascribe patch avoidance behavior to neurologically sophisticated organisms, but here we show identical behavior by a protist - the amoeboid slime mold Physarum polycephalum. This unicellular organism uses an externalized spatial memory system by depositing behind it a trail of extracellular slime. By subjecting amoebae to Y-maze choices, we found that the organism discriminates between slime deposited by conspecifics and heterospecifics and avoids areas where others have been previously. We argue that slime molds use the presence of extracellular slime to preferentially explore novel areas. If the organism perceives the presence of food, it will enter this area even if extracellular slime is present. Thus, extracellular slime does not serve as a repellent but as a cue that an area is most likely devoid of food sources.