Natural Trap Cave (Bighorn Mountains, Wyoming) preserves an abundance of fossil remains from extinct Late Pleistocene fauna and is situated near a past migration route that likely connected populations in Eastern Beringia and the contiguous US—the ice-free corridor between the Cordilleran and Laurentide icesheets. Some palaeontological evidence supports a correspondingly high affinity between fauna recorded in Natural Trap Cave and Eastern Beringia versus elsewhere in the contiguous US, but this hypothesis has not yet been extensively tested using genetic data. In the present study, we analysed 16 horse specimens and one camel specimen from Natural Trap Cave. Of the horse specimens we analysed, we obtained 10 unique and previously unreported mitochondrial haplotypes belonging to two distinct (extinct) genetic clades—two haplotypes corresponded to a caballine horse (Equus sp.) and eight corresponded to the stilt-legged horse (Haringtonhippus francisci). With only one exception, it appears these newly sequenced individuals all shared a common ancestor more recently with Eastern Beringian individuals than with others from the contiguous US. In addition, mitochondrial data from a specimen assigned to Camelops sp. revealed that it shares a closer affinity with specimens from the Yukon Territory than those from Idaho or Nevada, though all appear to belong to a single species (“yesterday’s camel”; Camelops cf. hesternus). Together, these results are consistent with a high level of genetic connectivity between horse and camel populations in the Bighorn Mountains and Eastern Beringia during the Pleistocene.