Background: Traditional vector control approaches such as source reduction and insecticide spraying have limited effect on reducing Aedes aegypti population. The endosymbiont Wolbachia is pointed as a promising tool to mitigate arbovirus transmission and has been deployed worldwide. Models predict a rapid increase on the frequency of Wolbachia-positive Ae. aegypti mosquitoes in local settings, supported by cytoplasmic incompatibility (CI) and high maternal transmission rate associated with the wMelBr strain. Methodology/principle findings: Wolbachia wMelBr strain was released for 20 consecutive weeks after receiving >87% approval of householders of the isolated community of Tubiacanga, Rio de Janeiro. wMelBr frequency plateued~40% during weeks 7-19, peaked 65% but dropped as releases stopped. A high (97.56%) maternal transmission was observed. Doubling releases and deploying mosquitoes with large wing length and low laboratory mortality produced no detectable effects on invasion trend. By investigating the lab colony maintenance procedures backwardly, pyrethroid resistant genotypes in wMelBr decreased from 68% to 3.5% after 17 generations. Therefore, we initially released susceptible mosquitoes in a local population highly resistant to pyrethroids which, associated with the over use of insecticides by householders, ended jeopardizing Wolbachia invasion. A new strain (wMelRio) was produced after backcrossing wMelBr females with males from field to introduce mostly pyrethroid resistance alleles. The new strain increased mosquito survival but produced relevant negative effects on Ae. aegypti fecundity traits, reducing egg clutche size and egg hatch. Despite the cost on fitness, wMelRio successful established where wMelBr failed, revealing that matching the local population genetics, especially insecticide resistance background, is critical to achieve invasion. Conclusions/significance: Local householders support was constantly high, reaching 90% backing on the second release (wMelRio strain). Notwithstanding the drought summer, the harsh temperature recorded (daily average above 30°C) did not seem to affect the expression of maternal transmission of wMel on a Brazilian background. Wolbachia deployment should match the insecticide resistance profile of the wild population to achieve invasion. Considering pyrethroid-resistance is a widely distributed phenotype in natural Ae. aegypti populations, future Wolbachia deployments must pay special attention in maintaining insecticide resistance in lab colonies for releases.