Aedes aegypti mosquitoes carrying self-spreading, virus-blocking Wolbachia bacteria are being deployed to suppress dengue transmission. However, there are challenges in applying this technology in extreme environments. We introduced two Wolbachia strains into Ae. aegypti from Saudi Arabia for a release program in the hot coastal city of Jeddah. Wolbachia reduced infection and dissemination of dengue virus (DENV2) in Saudi Arabian mosquitoes and showed complete maternal transmission and cytoplasmic incompatibility. Wolbachia reduced egg hatch under a range of environmental conditions, with the Wolbachia strains showing differential thermal stability. Wolbachia effects were similar across mosquito genetic backgrounds but we found evidence of local adaptation, with Saudi Arabian mosquitoes having lower egg viability but higher adult desiccation tolerance than Australian mosquitoes. Genetic background effects will influence Wolbachia invasion dynamics, reinforcing the need to use local genotypes for mosquito release programs, particularly in extreme environments like Jeddah. Our comprehensive characterization of Wolbachia strains provides a foundation for Wolbachia-based disease interventions in harsh climates.