With the recent finding of Paratrechina (broad sense) paraphyly, only Paratrechina longicornis remained in a redefined genus. As one of the most widely distributed ant species due to human transfer around the world, there is much interest in the biology of P. longicornis. One issue concerning P. longicornis has been as to where exactly the species is native, with both African and Asian native ranges being invoked in the literature. Here we report the discovery of a second species within Paratrechina. This species, P. zanjensis, is native to Africa (known from Angola, Mozambique and Tanzania), where it appears to be a dry miombo woodland species. Given the discovery of this new species, a reevaluation of the morphological definition of Paratrechina is provided; also provided is an updated generic level identification key. Given the available distribution information on P. longicornis, we conclude that P. longicornis remains most likely native to southeastern Asia, and that the discovery of a new species native to Africa makes Paratrechina yet another example of an ant genus that possesses an Afro-Asian distribution.