The Mexican Hairless dog, or Xoloitzcuintle, is a breed characterised by a sparse hair coat and a severe oligodontia. This phenotype is a consequence of Canine Ectodermal Dysplasia (CED) caused by a mutation on the FoxI3 autosomal gene. First accounts of hairless dogs in Mexico are dated to the 16th century CE, according to the historical record, but pre-Hispanic dog skeletons presenting missing and abnormally shaped teeth have been interpreted as earlier evidence of hairless dogs. However, several questions remain unanswered regarding the timing of apparition of this phenotype and its relationship with modern hairless breeds. In this paper, we review the morphological characteristics of potential hairless dogs and we apply ancient mitochondrial DNA analyses along with radiocarbon dating to eight archaeological dog mandibles from Tizayuca, Basin of Mexico, presenting anomalies that could be attributed to a CED. The archaeological dogs were dated between 1620 and 370 years BP. Among these eight individuals, we identify four different mitochondrial haplotypes including two novel haplotypes. The dogs from the Basin of Mexico display a very high genetic diversity and continuity from the Classic to the Postclassic. However, our attempt at amplifying the FoxI3 mutation was unsuccessful. Finally, we show that some haplotypes are present in both archaeological dogs and modern hairless breeds, perhaps reflecting their maternal ancestry.