Ten tijde van Sint Augustinus (4e eeuw) lag Partenia in "Mauretania Sitifiana", m.a.w. in de streek van Setif, op de hoogvlaktes van het huidige Algerije.
Van dit bisdom is praktisch niets bekend. Wanneer werd het opgericht? Waar was het precies gelokaliseerd? Het heeft geen zin om er vandaag naartoe te gaan. Het is verdwenen onder het zand.

In 484 nam Huneric, de koning van de Vandalen, het land in. Hij riep de bisschoppen bijeen in Carthago, in zijn paleis. Rogatus, bisschop van Partenia, werd vervolgd en verbannen.

Partenia, dat nu niet meer bestaat, is tot symbool geworden van allen die het gevoel hebben dat ze voor de samenleving of voor de kerk niet meer bestaan. Het is een immens bisdom, zonder grenzen, waarin de zon nooit ondergaat.