Wolbachia, a Gram-negative intracellular bacterium, naturally infects many arthropods, including mosquito vectors responsible for the spread of arboviral diseases such as Zika, chikungunya, and dengue fever. Certain Wolbachia strains are involved in inhibiting arbovirus replication in mosquitoes, and this phenomenon is currently being studied to combat disease vectors. A study was conducted in four states in north-eastern India to investigate the presence of natural Wolbachia infection in wild-caught Aedes albopictus and Aedes aegypti mosquitoes, the established vectors of dengue. The detection of a Wolbachia infection was confirmed by nested PCR and sequencing in the two mosquito species Ae. aegypti and Ae. albopictus. Positivity rates observed in Ae. aegypti and Ae. albopictus pools were 38% (44 of 115) and 85% (41 of 48), respectively, and the difference was significant (chi-square = 28.3174, p = 0.00000010). Sequencing revealed that all detected Wolbachia strains belonged to supergroup B. Although Wolbachia infection in Ae. aegypti has been previously reported from India, no such reports are available from north-eastern India. Data on naturally occurring Wolbachia strains are essential for selecting the optimal strain for the development of Wolbachia-based control measures. This information will be helpful for the future application of Wolbachia-based vector control measures in this part of the country.