Fleas (Siphonaptera) are ubiquitous blood-sucking pests of animals worldwide and are vectors of zoonotic bacteria such as Rickettsia and Bartonella. We performed Ion Torrent PGM amplicon sequencing for the bacterial 16S rRNA gene to compare the microbiome of the ubiquitous cat flea (Ctenocephalides f. felis) and the host-specific echidna stickfast flea (Echidnophaga a. ambulans) and evaluated potential bias produced during common genomic DNA-isolation methods. We demonstrated significant differences in the bacterial community diversity between the two flea species but not between protocols combining surface sterilisation with whole flea homogenisation or exoskeleton retention. Both flea species were dominated by obligate intracellular endosymbiont Wolbachia, and the echidna stickfast fleas possessed the endosymbiont Cardinium. Cat fleas that were not surface sterilised showed presence of Candidatus ‘Rickettsia senegalensis’ DNA, the first report of its presence in Australia. In the case of Rickettsia, we show that sequencing depth of 50 000 was required for comparable sensitivity with Rickettsia qPCR. Low-abundance bacterial genera are suggested to reflect host ecology. The deep-sequencing approach demonstrates feasibility of pathogen detection with simultaneous quantitative analysis and evaluation of the inter-relationship of microbes within vectors.