In biological control, successful establishment of a natural enemy species depends on its adaptability in the introduced range including its ability to re-establish desired ecological interactions with the pest. These are affected by genetic parameters hitherto largely unresolved in biological control. The larger grain borer (LGB), Prostephanus truncatus, an invasive species from meso-America, is the most important post-harvest pest of maize in Africa. We studied the genetic structure of Teretrius nigrescens, a predatory beetle previously released for the control of the pest in Africa, to test the hypothesis that establishment patterns were a result of ecotype–environment mismatch and to follow up on our earlier reports of distinct lineages of the predator. We studied 13 populations of T. nigrescens, using 16 polymorphic microsatellite markers. Five genetic populations with a hierarchical structure and significant isolation by distance were detected. The most diverse population was found in southern Mexico, consistent with earlier lineage coexistence observations. Populations introduced to Africa maintained genetic similarity to local geographic populations of their area of origin. The more successful Benin releases were also more genetically diverse. Loss of rare alleles and a higher frequency of existing private alleles in some populations indicated population expansions following bottleneck events. Sustainable biological control should accommodate pest and natural enemy species, and monitor genetic changes associated with introduction and release.