Algeria ranks second after Afghanistan for the incidence of cutaneous leishmaniasis (CL) worldwide. Here, we report a 34-years retrospective analysis of CL in Algeria and focused on the most affected region, the M’Sila province. All 66 cutaneous isolates corresponded to Leishmania (L.) major. Our study of the sandfly and rodent fauna further highlighted the high density of Phlebotomus papatasi and additional phlebotomine species of medical importance, not previously identified in M’Sila. Wild rodents belonging to nine species were trapped in M’Sila, and Psammomys obesus and Meriones shawi were found infected by L. major. In addition, Leishmania infantum was isolated from two visceral leishmaniasis cases, one dog and its proven vectors (P. perniciosus, P. longicuspis, and P. perfiliewi) inventoried during the survey. The high incidence of CL in the M’Sila province is likely a consequence of the increase in minimum temperatures recorded that constitutes suitable conditions for establishing a high endemicity and leads to an explosive rise in leishmaniases cases in this region. A thorough investigation of the underlying risk factors is urgently needed to detect new cases earlier. All these would improve the preparedness to fight the disease.