Genetic manipulations of insect populations for pest control have been advocated for some time, but there are few cases where manipulated individuals have been released in the field and no cases where they have successfully invaded target populations. Population transformation using the intracellular bacterium Wolbachia is particularly attractive because this maternally-inherited agent provides a powerful mechanism to invade natural populations through cytoplasmic incompatibility. When Wolbachia are introduced into mosquitoes, they interfere with pathogen transmission and influence key life history traits such as lifespan. Here we describe how the wMel Wolbachia infection, introduced into the dengue vector Aedes aegypti from Drosophila melanogaster, successfully invaded two natural A. aegypti populations in Australia, reaching near-fixation in a few months following releases of wMel-infected A. aegypti adults. Models with plausible parameter values indicate that Wolbachia-infected mosquitoes suffered relatively small fitness costs, leading to an unstable equilibrium frequency <30% that must be exceeded for invasion. These findings demonstrate that Wolbachia-based strategies can be deployed as a practical approach to dengue suppression with potential for area-wide implementation.