Wolbachia are intracellular, maternally transmitted bacteria considered the most abundant endosymbionts found in arthropods. They reproductively manipulate their host in order to increase their chances of being transmitted to the offspring, and currently are being used as a tool to control vector-borne diseases. Studies on distribution of Wolbachia among its arthropod hosts are important both for better understanding why this bacterium is so common, as well as for its potential use as a biological control agent. Here, we studied the incidence of Wolbachia in a broad range of insect species, collected from different regions of Brazil, using three genetic markers (16S rRNA, wsp and ftsZ), which varied in terms of their sensitivity to detect this bacterium. The overall incidence of Wolbachia among species belonging to 58 families and 14 orders was 61.9%. The most common positive insect orders were Coleoptera, Diptera, Hemiptera and Hymenoptera, with Diptera and Hemiptera having the highest numbers of Wolbachia-positive families. They included potential human disease vectors whose infection status has never been reported before. Our study further shows the importance of using quantitative polymerase chain reaction for high-throughput and sensitive Wolbachia screening.