ニューメキシコ州の歴史（History of New Mexico）は、1500年代にこのエリアを探険したスペイン人が、インディアンのプエブロ族と遭遇した時に初めて記録された。それ以来、このエリアはスペイン、メキシコ、アメリカ合衆国によって統治された。
プエブロ族の時代

ニューメキシコ州での人間の居住は、野営地と石器の証拠が残されている狩猟採集社会のクローヴィス文化があった1万年以上前にまでさかのぼる。農業の発明の後、古代プエブロ人が、石またはアドベレンガ(日干ししたレンガ)で家を建てて居住していた。古代プエブロ人は紀元1000年頃に最盛を迎えた。その後の気候の変化は、大きな川沿いの地域への移住を導き、そこに最初に居住した現代のプエブロ族の文化が進化した。

有史以前のインディアンの遺跡は、現在のサンタフェにその存在を示している。アルバカーキ近くのサンディア山脈にある洞窟には、新世界での最も早い居住者の痕跡が見られる。プエブロ族は、1200年代に栄えた定住性の文化を構築し、リオ・グランデ川流域に居住し、小さな集落を建築した。

スペイン人は、16世紀にプエブロ文化に遭遇した。1527年のナルバエス遠征隊の4人の生存者のうちの一人であるカベサ・デ・バカが、その困難な探険の途中、ニューメキシコのどこかにある素敵な町についてインディアンから話を聞いたことを、1535年に記述した。それは当時ヌエバ・エスパーニャの植民者に広まっていたシボラの7都市伝説と重なり、それを検証するための遠征に任命されたマルコス・デ・ニサは、帰国後、シボラの存在を熱心に認めた。しかしこれは、フランシスコ・バスケス・デ・コロナドによる、1540年から1542年の間の大規模な探険によって、嘘であったことが明した。コロナドは1541年に、今日コロナド国有記念物に保存されている出土した集落の近くでキャンプをした。リオ・グランデ川流域の上流を探険している間の彼のプエブロ族への虐待は、スペイン人のニューメキシコの征服に対するその後の敵意へと通じることになった。

現在のニューメキシコ州の3大プエブロは、ズニ、サントドミンゴ、そしてラグーナである。
スペイン植民地時代
スペイン人による探険と植民地化「スペインによるアメリカ大陸の植民地化」も参照

フランシスコ・バスケス・デ・コロナドは、1540年から1542年の間、メキシコのコンポステラに大規模な探険隊を集めた。カベサ・デ・バカが、フロリダからメキシコまでの8年間にわたる悲惨な旅の末に、ついに到着したといわれていた、伝説のシボラの7つの黄金都市を発見するためであった。カベサ・デ・バカと3人の仲間は、1527年6月17日にフロリダへ向かって、80頭の馬と残りの探険家すべてを失ったパンフィロ・デ・ナルバエス探険隊の生き残りだった。これらのカベサ・デ・バカ他４人の生存者たちは、太平洋沿岸にあるメキシコのシノロアに到着するのに大変な8年を費やし、その間に多くのインディアン部族を訪ねた。

コロナドと彼の支援者たちは、乗用と運搬用に馬とラバを1300頭、それに携帯用食糧として100個の羊と牛の頭を手に入れ、この不運な事業に財産を費やした。コロナドたちは1541年、いくつかのアドベで造られたプエブロ集落を見つけることはできたが、黄金都市は発見できなかった。アメリカ南西部やグレートプレーンズでのさらなる広範囲にわたる探険でも、素晴らしい黄金の街はどこにもなかった。すっかり落ち込んで貧窮したコロナドたちは、ニューメキシコを後にしてメキシコへ帰った。この時、おそらくコロナドの残した最もすばらしい遺産は、アメリカの平野での数頭の馬と牛の損失だった。 これらの動物は5年毎に頭数が倍増して、すぐに荒野でスクスクと育った。後に荒野に群れを成すほどになるスペインの牛と同様に、100?150年後にはほとんどすべてのインディアンたちが乗ることになる馬の先駆けになった。

コロナドの50年以上後の1598年、フアン・デ・オニャーテは、リオ・グランデ川の上に、現在のニューメキシコ州でのヨーロッパ人による最初の開拓地、サンフアンを創った。オニャーテは、ヌエバ・エスパーニャから遠く離れた植民地までの、距離にして700マイル(1100キロ)の「エル・カミノ・レアル」(英:The Royal Road)と名付けられた陸路を開拓した。オニャーテは、新しいヌエボ・メヒコ州(スペイン領のニューメキシコ州)の最初の総督になった。アコマ・プエブロにいるインディアンたちは、 このスペイン人の台頭に対して反抗したが、激しい抑圧に直面してしまった。アコマとの戦いで、彼らは従属を拒否し、オニャーテは11人の兵士と2人の使用人を失ったが、数百人のインディアンたちを殺して24人を処刑した。カトリックの伝道の名目で植民地にミッション(伝道所)を建設していたフランシスコ会は、相変わらずプエブロの人々に対してキリスト教改宗を強制し、反発を受けていた。

1609年、後のヌエバメヒコ州の総督となるペドロ・デ・ペラルタは、 サングレ・デ・クリスト山脈のもとにサンタフェの地を開拓した。サンタフェは、この建設時以来ずっとニューメキシコ州の州都であるため、米国で最古の州都である。1610年、ペラルタは総督邸を建てた。植民地の繁栄には失敗したが、いくつかの伝道所は残った。スペイン人開拓者たちは現在のアルバカーキ(1706年に創設された)の場所に1600年代中頃には到着した。宣教師たちはインディアンをキリスト教に改宗させようとしたが、ほとんど成功しなかった。
プエブロの反乱詳細は「プエブロの反乱」を参照

プエブロ族の伝統的な経済は、ヌエバ・エスパーニャのエンコミエンダ制によって混乱させられた。