Certain strains of the endosymbiont Wolbachia have the potential to lower the vectorial capacity of mosquito populations and assist in controlling a number of mosquito-borne diseases. An important consideration when introducing Wolbachia-carrying mosquitoes into natural populations is the minimisation of any transient increase in disease risk or biting nuisance. This may be achieved by predominantly releasing male mosquitoes. To explore this, we use a sex-structured model of Wolbachia-mosquito interactions. We first show that Wolbachia spread can be initiated with very few infected females provided the infection frequency in males exceeds a threshold. We then consider realistic introduction scenarios involving the release of batches of infected mosquitoes, incorporating seasonal fluctuations in population size. For a range of assumptions about mosquito population dynamics we find that male-biased releases allow the infection to spread after the introduction of low numbers of females, many fewer than with equal sex-ratio releases. We extend the model to estimate the transmission rate of a mosquito-borne pathogen over the course of Wolbachia establishment. For a range of release strategies we demonstrate that male-biased release of Wolbachia-infected mosquitoes can cause substantial transmission reductions without transiently increasing disease risk. The results show the importance of including mosquito population dynamics in studying Wolbachia spread and that male-biased releases can be an effective and safe way of rapidly establishing the symbiont in mosquito populations.