Background: The malaria vector Anopheles arabiensis exhibits greater behavioural and ecological plasticity than the other major vectors of the Anopheles gambiae complex, which presents challenges for major control methods. This study reports for the first time the presence of An. arabiensis in Antula, a suburb of Bissau city, the capital of Guinea Bissau, where high levels of hybridization between Anopheles coluzzii and An. gambiae have been reported. Given that previous surveys in the area, based on indoor collections, did not sample An. arabiensis, the possibility of a recently introduced exophilic population was investigated. Methods: Larval and adult mosquito collections were carried out in Antula at the end of the rainy season of 2010. Anopheles gambiae species composition, determined by rDNA-IGS and SINE200X6.1 markers, was compared with four previously collected samples dating back to 1993. Analysis of ten microsatellites was used to estimate levels of genetic diversity, relatedness and to investigate demographic stability. Results: Anopheles arabiensis comprised 54.0% of larvae and 25.6% of adults collected in 2010, but was absent in all previous collections, a highly unlikely observation by chance if the population was stable. This species had the lowest levels of genetic diversity, highest relatedness and, along with An. gambiae, exhibited evidence of a recent population expansion. Conclusions: Results point to the presence of a previously undetected outdoor population of An. arabiensis in Antula, which appears to have expanded recently, highlighting the importance of complementing indoor-based mosquito collections with sampling methods targeting outdoor adults and immature stages for a more complete assessment of mosquito biodiversity. A change in temporal dynamics in the species complex composition was also detected. Coupled with previous evidence of asymmetric introgression from An. coluzzii to An. gambiae, this suggests that the study area may be subject to ecological changes with a potential impact on both the genetics of these species and on malaria transmission.