New Mexico binlerce yıldır insanlar tarafından yerleşilmiş bir bölgedir. Mogollonve Anasazigibi eski kültürler, Pueblo gibi yerli Amerikan kabileleri yaşamaktaydı. Avrupalılar 1500’lü yıllarda bölgeyi keşfettikleri sırada, Acoma, Laguna, San Juan, Santa Ana ve Zuni gibi kabileler yaşamaktaydı. Kerpiçten yapılmış çok katlı binalarda konaklamaktaydılar. Kasabalarını genellikle savunmasız kalmamaları açısında kayalık yerlerin kenarlarına inşa etmişlerdir. Bu bölgeye ilk olarak İspanyol kâşifler altın aramaya geldiler, 1600’lü yıllarda da İspanya’nın resmî kolonisi haline geldi. Sonraları buraya Hıristiyan misyonerler gelerek yerli halkı dinlerine geçmeye zorladılar. İsyan çıkaran yerli halk kısa bir süreliğine İspanyolları topraklarından attılar, ancak çok geçmeden İspanyollar geri döndü. İspanyollar ve yerli Amerikalı halk arasında sürekli bir kavga oldu. Bölge ticaret için önemli bir yer haline geldi. Meksikalı- Amerikalı Savaşı sonrasında New Mexico, 1850 yılında ABD’ye girdi. 1800’lerin sonundaki New Mexico’ya “Vahşi Batı” denir. Bu zamanlarda topraklarda az sayıda avukat, çokça yolsuzluk ve yasadışı olay vardı. O sıralarda bazı kasabalar kanun kaçaklarının, at hırsızlarının konakladığı, kumar oynadığı yerdi. Hatta en çok bilinen kanun kaçaklarından biri Billy the Kid’di. Eyalet 1912 yılında ABD’ye 47. eyalet olarak kabul edilmiştir. II. Dünya Savaşı sırasında uzak ve az sayıda nüfusa sahip olduğu için atom bombası geliştirilmesinde merkez olmuştur. İlk atom bombası Los Alamos Ulusal Laboratuarı’nda geliştirildi ve Trinity’de patlatıldı.