A total of 56 fleas were collected from mice, rats, and one hedgehog in national parks of mainland Portugal and the Madeira Island. All fleas were tested for the presence of bacteria of the genera Rickettsia and Bartonella using PCR assays. In fleas from mainland Portugal, we detected Rickettsia felis in one Archaeopsylla erinacei maura flea and in one Ctenophtalmus sp. In five Leptopsylla segnis fleas taken from rats in the Madeira Island, we identified Rickettsia typhi. In addition, in four fleas from the genera Ornithophaga and Stenoponia collect from mice and a rat in mainland Portugal, we detected the presence of two new Bartonella genotypes closely related to Bartonella elizabethae. Our findings emphasize the potential risk of flea-transmitted infections in mainland Portugal and the Madeira archipelago, and extend our knowledge of the potential flea vectors of human pathogens.