Mycobacterium leprae, the causative agent of Hansen’s disease (leprosy), has plagued humans and other animal species for millennia and remains of concern to public health throughout the world today. Recent research into the expanded use of medical tissues preserved as formalin-fixed, paraffin-embedded samples (FFPE), opened the door for the study of M. leprae DNA from preserved skin samples. However, problems persist with damage to the DNA including fragmentation and cross linkage. This study evaluated two methods commonly used for the recovery of host DNA from FFPE samples for their efficacy in extracting pathogen DNA (hot alkaline lysis protocol and QIAGEN QIAamp FFPE DNA kit). Twenty FFPE skin samples collected from 1995-2015 from human subjects in the Pacific Islands suffering from M. leprae infection, each exhibiting a range of bacillary loads, were analyzed to determine which extraction method was most successful in terms of ability to consistently yield reliable, robust traces of M. leprae infection. This study further examined these samples to understand the phylogeny of leprosy in the region, where gaps in the evolutionary history of M. leprae persist. DNA recovery from paired samples was similar using either method. However, by extending the incubation time of post-paraffin removal sample lysis, both protocols were more likely to yield positive traces of M. leprae, with this enhancement being especially evident in paucibacillary samples with low bacterial presence. The qPCR assay findings suggest that the hot alkaline procedure is most likely to yield positive identification of infection in these traditionally challenging samples.