Delineating the colony identity of Coptotermes gestroi (Wasmann) is a core issue of colony elimination in the implementation of subterranean termite baiting systems. Invasion history is believed the possible cause of genetic variabilities among colonies. Haplotype network analysis of mitochondrial cytochrome c oxidase subunit II revealed the multiple origins of American C. gestroi from the Philippines and Southeast Asia and the Taiwan population only from the Philippines. We further developed 21 new microsatellite markers for the comparison of genetic variabilities on colony delineation of C. gestroi colonies from South Florida (invaded ~30 years; 3–7 generations) and Taiwan (~110 years; 13–27 generations). The present microsatellite markers with 1–4 alleles per locus have validated the effectiveness of colony delineation for three incipient colonies reared in the laboratory and three field colonies from Taiwan. Genetic admixture of the Floridian C. gestroi probably caused by recent invasion history, multiple invasions, and anthropogenic activities among regions. A possible introduction event likely occurred through human-mediated activities between Fort Lauderdale and Miami. Overall, these new microsatellite markers provide suitable and efficient candidate genetic markers for colony delineation of C. gestroi to consolidate the effectiveness of the colony elimination system in termite management.