Coğrafi bölgenin M.Ö 12. yy.a kadar dönemi karanlıktır. Bir görüşe göre Phygie "Frigler" in Boğazlar yolu ile Anadoluya sarkarak Hititleri yenilgiye uğrattıkları, sonradan kendi adlarını verdikleri yöreyi yurt edindikleri dönemdir. M.Ö. 12. yy.'a kadar Frigler bölgeyi ellerinde tutmuş, ardından Yunanistan'ın Megara şehrinden kendilerine yeni bir yer aramak için yola çıkan göçmen bir grup, şimdiki Başiskele mevkiinde Astakos adını verdikleri şehri kurmuşlardır.
Diğer bir görüşe göre ise, Trakyadan Anadolu içlerine göçen Frigler daha sonra Mysiens "Misya"lılar İzmit çevresinin ilk belirli halklarıdır. M.Ö 712 yılına ait bir yüzünde kent tanrıçası Olbia, diğer yüzünde kent arması İstakoz resmi bulunan -Devlet olmanın simgesi olmak üzere- para basması bir kent devleti durumunu oluşturur. Yunanca Astakos kelimesi İzmit körfezinde çok avlanan Istakoz deniz hayvanına delalet eder.
Astakos'u ele geçiren Bithynialı Dedalses Bithynia Krallığını kurdu.