Desain dasar dari segel negara bagian New Mexico diyakini berasal dari tahun 1860-an, meskipun desain akhir untuk segel tersebut tidak diadopsi secara resmi sampai tahun 1913. Ini menggambarkan seekor elang botak, burung nasional Amerika Serikat, dengan sayapnya. melilit seekor elang coklat Meksiko. Gambar pada stempel negara bagian New Mexico ini melambangkan status New Mexico sebelumnya sebagai bagian dari negara Meksiko. Elang coklat Meksiko di segel negara bagian New Mexico digambarkan memegang kaktus di cakarnya dan ular di paruhnya. Di bawah burung-burung, sebuah pita menampilkan moto Latin negara bagian New Mexico, “Crescit Eundo,” yang biasanya diterjemahkan berarti, “Itu tumbuh seiring berjalannya waktu,” dan segel itu berbatasan dengan kata-kata “Segel Besar Negara Bagian New Mexico” dan tahun ketika New Mexico secara resmi menjadi negara bagian, 1912.
Wilayah yang membentuk negara bagian Amerika modern New Mexico sebelumnya dianggap sebagai bagian dari negara Meksiko, hingga sekitar tahun 1846. Saat ini, New Mexico menjadi wilayah Amerika Serikat. Wilayah New Mexico mengadopsi segel teritorial pertamanya pada tahun 1851. Stempel negara bagian New Mexico yang sekarang digunakan berbeda dalam desainnya, yang menggambarkan elang botak dan elang coklat Meksiko, bukan hanya elang botak. Desain ini, diyakini mulai digunakan sekitar tahun 1860-an, mungkin dibuat oleh seorang pejabat pemerintah kecil yang identitasnya sekarang hilang.
Sekretaris Teritorial WG Ritch biasanya dikreditkan dengan menambahkan moto Latin New Mexico ke segel pada tahun 1882. Badan legislatif teritorial New Mexico secara resmi menyetujui desain yang diubah ini pada tahun 1887. Ketika New Mexico diberikan status negara bagian pada tahun 1912, legislatif negara bagian membentuk komite khusus untuk memilih sebuah desain untuk segel negara. Komite ini diyakini terdiri dari gubernur, sekretaris negara, hakim agung, dan jaksa agung.
Pada tahun 1913, komite memilih untuk mempertahankan desain segel teritorial untuk segel negara bagian New Mexico. Desain akhir mengubah kata-kata di sekitar tepi segel menjadi “Segel Besar Negara Bagian New Mexico,” daripada, “Wilayah New Mexico.” Tanggal pada desain akhir juga diubah, dari tahun 1850, ketika New Mexico pertama kali menjadi wilayah, menjadi tahun 1912, ketika menjadi negara bagian.