Spiral-shaped foraging trace fossils, assigned to the grapho glyptid cf. Spirorhaphe azteca, are reported from an Early Permian intertidal flat in the Robledo Mountains of southern New Mexico, USA. Remarkably similar spiral-shaped structures are produced in modern intertidal flats by the paraonid polychaete Paraonis fulgens, and function as traps to capture mobile microorganisms migrating in the sediment in response to tides. We envisage a similar function for the Early Permian trace fossils. Previous studies have suggested that the lack of P. fulgens–type traces from ancient intertidal deposits indicates that such behavior only evolved geologically recently in such settings. However, this report demonstrates that such specialized foraging behavior was present in intertidal settings by at least the Early Permian. Graphoglyptids are typical of deep-marine settings, and characteristic of the Nereites ichnofacies. This represents their first undoubted occurrence in intertidal facies in the geological record. We postulate that the occurrence of graphoglyptids in deep-marine and intertidal settings is related to the predictability of resources. The scarcity of intertidal graphoglyptids in the geological record is most likely a preservational effect.