Okres republiki mały|Ruiny Gortyny, stolicy prowincji Po podboju Krety oba obszary zostały połączone w jeden organizm administracyjny. Dokładna data utworzenia wspólnej prowincji pozostaje przedmiotem dyskusji – część badaczy wiąże ją z reorganizacją Pompejusza około 67 p.n.e., podczas gdy inne interpretacje wskazują na okres wojen domowych i ostateczne uporządkowanie administracji przez Augusta.
W końcowym okresie republiki rzymskiej sytuacja prowincji była niestabilna. Cyrenajka, położona pomiędzy Egiptem a Afryką Północną, znalazła się w centrum rywalizacji politycznej podczas wojen domowych. W 44 p.n.e. Cyrenajka została przydzielona Kasjuszowi, a Kreta Brutusowi, jednak obaj nie objęli faktycznie swoich prowincji, angażując się w walkę o władzę.
W latach 30. I wieku p.n.e. część Cyrenajki znalazła się pod kontrolą Marka Antoniusza, który przekazał znaczną część dawnych terytoriów ptolemejskich Kleopatrze VII i jej rodzinie. Po klęsce Antoniusza i Kleopatry w bitwie pod Akcjum w 31 p.n.e. Rzym odzyskał bezpośrednią kontrolę nad tymi ziemiami.