All'epoca di Sant'Agostino (IV secolo), Partenia figurava nella "Mauritania Sitifiana", in altri termini nella regione di Sétif, sugli altipiani dell'attuale Algeria.
Di questa diocesi non si sa praticamente nulla: né sulla sua data di nascita e neppure sulla sua esatta localizzazione. Inutile recarsi sul posto oggi: essa è scomparsa sotto le sabbie.
Nel 484 Unerico, il re dei Vandali, invade il paese e convoca i vescovi nel suo palazzo di Cartagine. Rogato, vescovo di Partenia, sarà perseguitato ed esiliato.

Dal momento che Partenia non esiste più, essa diventa il simbolo di tutti coloro che nella società come nella Chiesa hanno la sensazione di non esistere più. E' un'immensa diocesi senza frontiere in cui il sole non tramonta mai.