Wolbachia bacteria are known to cause deviations from random mating and affect sperm competition (SC) in some of their arthropod hosts. Because these effects could influence the effectiveness of Wolbachia in mosquito population replacement and suppression programs, we developed a theoretical framework to investigate them and we collected relevant data for the wMel infection in Aedes aegypti. Using incompatibility patterns as a measure of mating success of infected versus uninfected mosquitoes, we found some evidence that uninfected males sire more offspring than infected males. However, our theoretical framework suggests that this effect is unlikely to hamper Wolbachia invasion and has only minor effects on population suppression programs. Nevertheless, we suggest that mating effects and SC need to be monitored in an ongoing manner in release programs, given the possibility of ongoing selection for altered mating patterns.