Identifying the current geographic range of disease vectors is a critical first step towards determining effective mechanisms for controlling and potentially eradicating them. This is particularly true given that historical vector ranges may expand due to changing climates and human activity. The Aedes subgenus Stegomyia contains over 100 species, and among them, Ae. aegypti and Ae. albopictus mosquitoes represent the largest concern for public health, spreading dengue, chikungunya, and Zika viruses. While Ae. aegypti has been observed in the country of Zambia for decades, Ae. albopictus has not. In 2015 we sampled four urban and three rural areas in Zambia for Aedes species. Using DNA barcoding, we confirmed the presence of immature and adult Ae. albopictus at two sites: Siavonga and Livingstone. These genotypes seem most closely related to specimens previously collected in Mozambique based on CO1 sequence from mtDNA. We resampled Siavonga and Livingstone sites in 2019, again observing immature and adult Ae. albopictus at both sites. Relative Ae. albopictus frequencies were similar between sites, with the exception of immature life stages, which were higher in Siavonga than in Livingstone in 2019. While Ae. albopictus frequencies did not vary through time in Livingstone, both immature and adult frequencies increased through time in Siavonga. This report serves to document the presence of Ae. albopictus in Zambia, which will contribute to the process of determining the potential public health implications of this disease vector in Central Africa.