Teritorium Nové Mexiko (anglicky New Mexico Territory) vzniklo jako organizované teritorium USA dne 9. září 1850, a 6. ledna 1912 se stalo jako stát Nové Mexiko v pořadí již 47. spolkovým státem USA.
Západní část teritoria získaly USA od Mexika roku 1848 mírovou smlouvou z Guadelupe Hidalgo, zatímco východní část východně od řeky Rio Grande náležela před 9. září 1850 k Texasu, a součástí teritoria se stala na základě kompromisu roku 1850. Gadsdenovou koupí roku 1853 pak byl k teritoriu připojen nejjižnější pruh území moderních spolkových států Arizony a Nového Mexika.
V původním rozsahu z roku 1850 zahrnovalo teritorium Nové Mexiko většinu pozdějších států Arizona a Nové Mexiko, malou část moderního spolkového státu Colorada a část moderního státu Nevada jižně od 36° 30' s.š. 28. února 1861 se pak území teritoria zmenšilo ve prospěch nově vytvořeného teritoria Colorado, a vyčleněním teritoria Arizona 24. dubna 1863 západně od 109° z.d., pak získalo rozsah a hranice identické s moderním státem Nové Mexiko.
Během Americké občanské války se Arizona a Nové Mexiko staly sporným územím. Jižní část obou teritorii se jako konfederační teritorium Arizona dobrovolně připojila ke Konfederaci, a proběhla tu bitva o Glorietský průsmyk. Mezi lety 1878 a 1881 zde probíhala válka v Lincolnském okresu známá především díky působení legendárního zločince Billyho Kida.