New Mexico has the best record historically with having carried for presidential winners. It first voted in 1912 and sided with only one loser in the popular vote [and Electoral College]: 1976 Gerald Ford.
Nevada has voted the same as New Mexico with just one exception: 2000, a year which gave split results with one winner of the popular vote [who carried New Mexico] and one winner of the Electoral College [who carried Nevada].
Bush probably would've carried New Mexico in 2000 if it weren't for the early call of Florida.