Androctonus australis is one of the most ubiquitous and common scorpion species in desert and arid lands from North Africa to India and it has an important ecological role and social impact. The bacterial community associated to this arachnid is unknown and we aimed to dissect its species composition in the gut, gonads, and venom gland. A 16S rRNA gene culture-independent diversity analysis revealed, among six other taxonomic groups (Firmicutes, Betaproteobacteria, Gammaproteobacteria, Flavobacteria, Actinobacteria, and Cyanobacteria), a dominance of Mollicutes phylotypes recorded both in the digestive tract and the gonads. These related Mollicutes include two Spiroplasma phylotypes (12.5% of DGGE bands and 15% of clones), and a new Mycoplasma cluster (80% of clones) showing 16S rRNA sequence identities of 95 and 93% with Mollicutes detected in the Mexican scorpions Centruroides limpidus and Vaejovis smithi, respectively. Such scorpion-associated Mollicutes form a new lineage that share a distant ancestor with Mycoplasma hominis. The observed host specificity with the apparent phylogenetic divergence suggests a relatively long co-evolution of these symbionts with the scorpion hosts. From the ecological point of view, such association may play a beneficial role for the host fitness, especially during dormancy or molt periods.