The longhorn crazy ant, Paratrechina longicornis (Latreille), is a ubiquitous agricultural and urban pest that has invaded most tropical and subtropical regions. Although P. longicornis has been found worldwide for more than a century, the genetic structure, origin, and invasion history of this species have not yet been extensively studied, partially because of the limited number of genetic markers currently available. In the present study, we developed 36 polymorphic microsatellite markers for P. longicornis and characterized these markers by genotyping P. longicornis workers from 74 colonies in East and Southeast Asia. All loci were polymorphic, with the number of alleles per locus ranging from 3 to 18 (8.5 on average). Extremely high levels of heterozygosity were found in all populations, suggesting that workers are invariably produced from the mating of divergent queen and male lineages. Queens and males possess non-overlapping allele size ranges at 18 loci, indicating the potential resolving power of the subset of markers in inferring the history of queen and male lineages. Genetic differentiation among three studied populations was low yet significant and may likely reflect their close association with human activities. Overall, the new microsatellite markers developed in the present study serve as a practical tool to reconstruct routes of invasion and assess the population genetics of this invasive ant.