We report the first documented record for the Sooty Tern (Onychoprion fuscatus) in New Mexico and the fourth for the region of the southern Rocky Mountains and trans-Pecos Texas. The bird was found dead in moderately fresh condition on 8 July 2010 in the Laguna Grande area, near Carlsbad, Eddy County. It was brought to the Museum of Southwestern Biology where it was preserved as a study skin. A DNA analysis comparing the sequence of the specimen’s mitochondrial control region to a published population-genetic dataset on this species found that the sequence of the New Mexico tern was a perfect match with previously sequenced haplotypes from Puerto Rico and Ascension Island and ~2% divergent on average from all Sooty Terns previously sequenced from the Pacific and Indian oceans. Measurements of the specimen are consistent with a Caribbean origin. We surmise that this individual was carried inland from the Gulf of Mexico to southeastern New Mexico by the remnants of Hurricane Alex.