Leishmaniasis is an important travel-related parasitic infection in the United States. Treatment regimens vary by Leishmania species and require an accurate diagnosis. The sensitivity and specificity of diagnostic methods depend on the type and condition of specimen analyzed. To identify the best algorithm for detection of parasites in fresh and fixed tissue samples, we evaluated parasite cultures, two PCR methods, and Leishmania immunohistochemistry (IHC) in samples received by the CDC from 2012 through 2019. The sensitivity and specificity of IHC assays were evaluated in fresh specimens tested. Diagnostic accuracy for formalin-fixed tissue was evaluated by using PCR-based methods and IHC. Of 100 suspected cases with fresh tissue available, Leishmania spp. infection was identified by PCR in 56% (56/100) of specimens; from these, 80% (45/56) were positive by parasite culture and 59% (33/56) by IHC. Of 420 possible cases where only fixed specimens were available, 58% (244/420) were positive by IHC and/or PCR. Of these, 96% (235/420) were positive by IHC and 84% (204/420) by PCR-based methods. Overall parasite detection using all methodologies was similar for fresh and formalin-fixed tissue specimens (56% versus 58%, respectively). Although PCR-based methods were superior for diagnosis of leishmaniasis and species identification in fresh samples, IHC in combination with PCR increased the accuracy for Leishmania spp. detection in fixed samples. In conclusion, PCR is the most effective method for detecting Leishmania infection in fresh tissue samples, whereas for formalin-fixed samples, IHC and PCR-based methods should be used in combination.