Steinaldarminjar, sem fundust í grennd við Clovis, leiða í ljós búsetu manna fyrir rúmlega 10.000 árum.  Síðar stunduðu indíánar landbúnað með áveitum.  Anasazi-menningin blómstraði í San Juan-dalnum á fyrstu teinöld e.Kr.  Í kringum 1300 bjuggu þúsundir pueblo-indíána, afkomenda anasazi, í 18 borgum við Rio Grande-fljótið frá Taos suður til Isleta (neðan við núverandi Albuquerque).  Þeir stunduðu þróaða leirkeragerð, vefnað og skreytingalist og sum leirsteinshúsa þeirra voru 5 hæða há.  Á 15. öld olli koma hirðingjaættkvísla navajo og apache endalokum þessara lífshátta.  Þeir rændu auðugar byggðir Pueblo-indíánanna og hnepptu börn í þeirra í þrældóm.  Þessir atburðir ollu aldalöngu stríðsástandi milli þessara aðila.

Spænsk og mexíkósk yfirráð.  Árið 1539 heimsótti leiðangur undir forystu spænska fransiskóprestsins Marcos de Niza zuni pueblo-indíánana um leið og hann kannaði núverandi svæði Nýja-Mexíkó.  Næsta ár fór Francisco Coronado upp eftir Rio Grande.  Spænskt landnám nófst 1598 og Santa Fe var stofnuð 1610.  Spænsk yfirvöld þröngvuðu lögum sínum og reglum upp á pueblo-fólkið og snéru fjölda þess til kristni.  Tilraunir trúboða til að afnema hefðbundna trúarsiði þeirra ollu mikilli andstöðu.  Árið 1680 gerðu pueblo-indíánarnir uppreisn, drápu fjölda landnema og ráku aðra á flótta.

Spánverjar tóku Santa Fe aftur árið 1692 og fjórum árum síðar tókst þeim að ná öllu fyrra yfirráðasvæði undir sig á ný en viðurkenndu rétt pueblo-indíánanna til landa forfeðra sinna.  Nýjar borgir voru reistar á 18. öld.  Árið 1821 hurfu Spánverjar frá meginlandi Norður-Ameríku og Nýja- Mexíkó varð hérað hins nýja ríkis Mexíkó.

Yfirráð Mexíkó ollu miklum breytingum, því spænsk yfirvöld höfðu bannað útlendingum aðgang að Nýja-Mexíkó.  Nú hófust viðskipti við BNA og vöruflutningar hófust um Santa Fe leiðina frá St Louis í Missouri.  Bandarískir kaupmenn og skinnaveiðimenn flykktust til Santa Fe og Taos.  Strax gætti árekstra milli menningarheimanna.  Samskiptin hlóðust spennu, þegar hið nýja lýðveldi Texas reyndi að sölsa Nýja-Mexíkó undir sig árið 1841.  Landvinningasinnar í BNA kröfðust innlimunar alls suðvesturhluta Norður-Ameríku og Kaliforníu.  James K. Polk, forseti BNA, lýsti yfir stríði við Mexíkó 1846 og sendi Stephen Watts Kearny hershöfðingja með herinn til að ráðast inn í Nýja-Mexíkó.  Hann náði Santa Fe undir sig án þess að hleypa af skoti og lýsti Nýja-Mexíkó hluta BNA 18. ágúst 1846.

Sumir hispanar (blendingjar Spánverja og indíána) voru hlynntir hinum sigurælu Bandaríkjamönnum en indíánar í Taos Pueblo gerðu uppreisn og drápu Charles Bent, landstjórann, sem Kearny setti yfir héraðið.  Allir íbúarnir urðu borgarar BNA í samræmi við friðarsamningana, sem voru gerðir 1848 en sambandsþingið hafnaði þessu ákvæði og gerði svæðið, sem nú er Nýja-Mexíkó og Arizona, að héraði árið 1850 með málamiðlun um að Kalifornía yrði fylki í BNA.

Þessari niðurstöðu fylgdu áratugaátök milli indíána í Nýju-Mexíkó og Bandaríkjamanna.  Árið 1863 skildi sambandsþingið Arizona frá Nýja-Mexíkó.  Indíánarinir (navajo, apache og comanche) biðu ósigra gegn hersveitum BNA en nauðflutningur navajo-indíánanna (Gangan langa) til verndarsvæðisins Bosque Redondo mistókst og langsveltu fólkinu var snúið til heimalandanna við San Juan-ána árið 1868.  Samtímis þessum hörmungum efldist efnahagur héraðsins vegna tilkomu járnbrautanna til Santa Fe og að Kyrrahafinu, funda verðmætra jarðefna og fjölgunar ferðamanna.  Allt fram til aldamótanna 1900 álitu flestir borgarar BNA þetta hérað erlent land með skrítnu tungumáli, mat og klæðaburði.  Í hugum þeirra var þetta löglaust svæði með blóðugum átökum milli nautgripabúgarða, vaðandi spillingu í úthlutun lands og bústað útlaga í líkingu við Billy the Kid, sem var drepinn í byssubardaga í Fort Sumner árið 1881.  Hagstæðara alit á Nýju-Mexíkó fór að taka á sig mynd um aldamótin, þegar listamenn fóru að lýsa rómantískum töfrum Taos og Santa Fe og fólk fór að sækja til hinnar sólríku Albuquerque í heilsubótarskyni.

20. öldin.  Nýja-Mexíkó hafði stöðu héraðs í 62 ár, sumpart vegna þess, að íbúar þess óttuðust hærri skatta, ef það yrði fylki, og sumpart vegna þess, að sambandsstjórnin óttaðist, að lýðræði væri ekki framkvæmanlegt í spænskumælandi samfélagi.  Ríkisskólarnir hófu enskukennslu árið 1898 og Nýja-Mexíkó varð 47. fylki BNA 6. janúar 1912.

Elzta samfélag BNA var hrifið inn í nútímann, þegar leyniborgin Los Alamos, skammt frá Santa Fe, varð fæðingarstaður atómsprengjunnar árið 1943.  Tveimur árum síðar var fyrsta tilraunasprengjan í heiminum sprengd nærri Alamogordo sunnan Santa Fe.  Efnahagurinn vænkaðist við byggingu White Sands eldflaugaskotpallanna, Kirtland-flugherstövarinnar og kjarnorkurannsóknastöva í Albuquerque.  Það lifnaði yfir eyðimerkursvæðunum við fund olíu og náttúrugass og úrans í grennd við Grants.  Ferðaþjónustan varð að risaatvinnugrein en íbúarnir gættu þess vel, að missa ekki sjónar á uppruna sínum og menningu.