The Early Permian Robledo Mountains Formation of the Robledo Mountains in Don˜a Ana County, southern New Mexico, contains a diverse and abundant nonmarine trace fossil assemblage. Invertebrate and vertebrate trace fossils both occur in abundance and formed in an upper intertidal flat setting, a long way inshore and essentially under nonmarine conditions. Eighteen invertebrate ichnogenera, including 16 established ichnospecies, one reassigned ichnospecies and two new ichnospecies are described and illustrated, together with nine trace fossils described in open nomenclature. Previously described vertebrate ichnogenera and ichnospecies are reviewed and illustrated, together with the description of one new ichnospecies, totalling 10 ichnogenera and 13 ichnospecies. The ichnotaxonomy of Lithographus hieroglyphicus and Stiaria intermedia is also revised in the light of the material from the Robledo Mountains Formation of the Robledo Mountains and comparative Early Permian material from the Early Permian Standenbu¨hl Formation of the Saar-Nahe Basin near Frankfurt in Germany, the Hornburg, Oberhof, Rotterode and Eisenach Formations from the Thu¨ringer Forest in Germany, the Coconino Sandstone Formation of Arizona, and the Shalem Colony Formation of the Robledo Mountains. The invertebrate trace fossils from the Robledo Mountains Formation of the Robledo Mountains are dominated by arthropod trackways (Dendroidichnites irregulare, Diplichnites isp., Diplopodichnus biformis, Kouphichnium? isp., Lithographus hieroglyphicus, Octopodichnus cf. didactylus, Palmichnium macdonaldi, P. palmatum, P. pottsae and Stiaria intermedia), including several enigmatic arthropod trackways, as well as intergrading arthropod trackways (Diplichnites isp. x Diplopodichnus biformis, Diplopodichnus biformis x Dendroidichnites irregulare and cf. Lithographus x Diplopodichnus biformis), arthropod resting traces (cf. Lockeia, Rotterodichnium major, Selenichnites belosis isp. nov., Tonganoxichnus apacheensis comb. nov. and T. buildexensis), arthropod locomotory jumping traces (T. robledoensis), combined arthropod trackways and locomotory jumping traces (Stiaria intermedia x T. robledoensis), and arthropod grazing ⁄ raking traces (Stiallia pilosa and Striatichnium biflabellis isp. nov.). Invertebrate feeding traces (Treptichnus bifurcus) and grazing trails (Cochlichnus anguineus and looping trails) are present but rare. Trace fossils similar to the typically deep marine graphoglyptids are also present (cf. Spirorhaphe azteca), as well as horizontal helical-shaped burrows (Augerinoichnus helicoidalis) that may also have affinities with graphoglyptids. Further trace fossils described under open nomenclature include horizontal burrows and various enigmatic invertebrate trace fossils. The vertebrate trace fossils are dominated by tetrapod trackways (Batrachichnus salamandroides, Batrachichnus aff. salamandroides, Dimetropus nicolasi, D. leisneranius, Dromopus lacertoides, cf. Erpetopus, Limnopus vagus, Gilmoreichnus hermitanus and Hyloidichnus bifurcatus), whilst tetrapod swimming trackways (Lunichnium rotterodium, Serpentichnus robledoensis and S. sigmoidalis isp. nov.) and fish swimming trails (Undichna bina, U. britannica and Undichna? unisulca) are also present. The trace fossil assemblage can be considered as an example of the Scoyenia ichnofacies, although the presence of rare elements of the Mermia ichnofacies indicates that there are pre- and syndesiccation suites of trace fossils. Cluster analysis of trace fossil distributions across nonmarine depositional settings from the Early Permian of the south-west USA reveals patterns consistent with previous models, based on qualitative observations, of the distribution of vertebrate trace fossils and their palaeoenvironmental implications. Comparisons of analyses conducted using the vertebrate, invertebrate and all trace fossils from the assemblages reveals that, for assemblages covering a limited temporal and palaeogeographic scope, vertebrate trace fossils allow greater potential for identifying trace fossil associations that enable discrimination amongst different depositional settings than invertebrate trace fossils alone, whereas a holistic approach, utilizing all available trace fossil data, allows the greatest number of trace fossil associations, which correspond to different depositional settings, to be identified.