Bighorn sheep (Ovis canadensis) were not known to live on Tiburón Island, the largest island in the Gulf of California and Mexico, prior to the surprisingly successful introduction of 20 individuals as a conservation measure in 1975. Today, a stable island population of ~500 sheep supports limited big game hunting and restocking of depleted areas on the Mexican mainland. We discovered fossil dung morphologically similar to that of bighorn sheep in a dung mat deposit from Mojet Cave, in the mountains of Tiburón Island. To determine the origin of this cave deposit we compared pellet shape to fecal pellets of other large mammals, and extracted DNA to sequence mitochondrial DNA fragments at the 12S ribosomal RNA and control regions. The fossil dung was 14C-dated to 1476–1632 calendar years before present and was confirmed as bighorn sheep by morphological and ancient DNA (aDNA) analysis. 12S sequences closely or exactly matched known bighorn sheep sequences; control region sequences exactly matched a haplotype described in desert bighorn sheep populations in southwest Arizona and southern California and showed subtle differentiation from the extant Tiburón population. Native desert bighorn sheep previously colonized this land-bridge island, most likely during the Pleistocene, when lower sea levels connected Tiburón to the mainland. They were extirpated sometime in the last ~1500 years, probably due to inherent dynamics of isolated populations, prolonged drought, and (or) human overkill. The reintroduced population is vulnerable to similar extinction risks. The discovery presented here refutes conventional wisdom that bighorn sheep are not native to Tiburón Island, and establishes its recent introduction as an example of unintentional rewilding, defined here as the introduction of a species without knowledge that it was once native and has since gone locally extinct.