Pocas fuentes contemporáneas mencionan Creta durante el período comprendido entre el siglo IV y la conquista musulmana en los años 820.
[7][8][9] En el Synecdemus del siglo VI, Creta está marcada como gobernada por un consular, con capital en Gortyn, y hasta 22 ciudades.
[4] La población en este período se estima tan alta como 250.000, y era casi exclusivamente cristiana, a excepción de algunos judíos que viven en los principales centros urbanos.
Esto ha llevado a sugerir que la isla se constituyó como un thema en el siglo VIII, quizás ya en los años 730.
Los bizantinos emprendieron repetidas expediciones para hacerlos retroceder, y parecen haber designado estrategos para administrar las partes de la isla aún controlaban.
[2][7][18] La conquista musulmana de Creta comportó graves problemas para Bizancio, ya que hizo las costas e islas del mar Egeo vulnerables a la piratería.
[2][7] Durante la Cruzada, Creta parece haber sido otorgada a Bonifacio I, marqués de Montferrato como pronoia por el emperador Alejo IV Ángelo.