[1] The theme is attested for the first time in 863,[1][2][3] but it apparently existed as a separate district earlier: Nicolas Oikonomides interprets a reference by the Arab geographer al-Masudi to mean that it constituted first a kleisoura (a fortified frontier district).

[4][2] In addition, a version of the Life of the 42 Martyrs of Amorium mentions that Emperor Theophilos (r. 829–842) appointed a certain spatharios Kallistos as its doux in circa 842, making it the likely date of its elevation to a full theme (alongside neighbouring Chaldia).

In 1057, the local regiment, under Katakalon Kekaumenos, supported the uprising of Isaac I Komnenos.

[1][5] In the De Thematibus, Emperor Constantine VII Porphyrogennetos (r. 913–959) describes the theme as a small circumscription, encompassing, aside from Koloneia, Neocaesarea in the east, Arabraca, Mount Phalakros (probably modern Karaçam Dağı), Nicopolis and Tephrike.

[3][4] Porphyrogennetos also records that his father, Leo VI the Wise (r. 886–912), separated the tourma of Kamacha from Koloneia to form (along with Keltzene) the new theme of Mesopotamia.