Malaria still represents a potential public health issue in Italy, and the presence of former Anopheles vectors and cases imported annually merit continuous surveillance. In areas no longer endemic, the concurrent presence of gametocyte carriers and competent vectors makes re-emergence of local transmission possible, as recently reported in Greece. In October 2017, due to the occurrence of four suspected introduced malaria cases in the province of Taranto (Apulia region), entomological investigations were performed to verify the involvement of local anopheline species. In 2019–2020 entomological surveys were extended to other areas historically prone to malaria between the provinces of Taranto and Matera and the province of Foggia (Gargano Promontory). Resting mosquitoes were collected in animal shelters and human dwellings, larvae were sampled in natural and artificial breeding sites, and specimens were both morphologically and molecularly identified. A total of 2228 mosquitoes were collected, 54.3% of which were anophelines. In all the investigated areas, Anopheles labranchiae was the most widespread species, while Anopheles algeriensis was predominant at the Gargano sites, and Anopheles superpictus and Anopheles plumbeus were recorded in the province of Matera. Our findings showed a potentially high receptivity in the surveyed areas, where the abundance of the two former malaria vectors, An. labranchiae and An. superpictus, is related to environmental and climatic parameters and to anthropic activities.