Организации византийского флота в VIII–XI вв. Карависианы были заменены на более сложную систему, состоящую из трех элементов, которые с незначительными изменениями просуществовали до XI в.: центральный имперский флот, базировавшийся в Константинополе, небольшое количество крупных региональных команд — морских фем, или независимых флотских подразделений, называемых друнгариями, — и большое число местных эскадр, которые чаще всего выполняли чисто оборонительные и полицейские задачи в интересах наместников провинций[1248]. В отличие от римского флота, где провинциальные флоты численно уступали центральному флоту и включали в себя только легкие суда, византийские региональные флоты, как правило сами, по себе представляли мощную военную силу[1249].

Военный флот столицы сыграл центральную роль в отражении арабской осады Константинополя[1250], но неясно, существовал ли императорский флот (βασιλικὸν πλώιμον) в качестве отдельного формирования военного флота в VII–VIII вв. Должность его командующего, друнгария флота, впервые упоминается в «Тактиконе» Успенского в 842–843 гг. Кроме того, отсутствуют какие-либо упоминания о существовании крупного флота в Константинополе в течение VIII в. Поэтому Э. Арвейлер считала датой создания императорского флота начало IX в.[1251] С этого времени он представлял собой основной резерв и составлял главное ядро во время различных морских походов византийцев[1252].

Первой собственно морской фемой (греч. θέμα ναυτικόν) была фема Киверриотов (греч. θέμα Κιβυῤῤαιοτῶν). Ее задача в основном состояла в том, чтобы предоставлять по требованию командования суда и войска. Кивирреоты получают свое имя от города Кибирра, причем неясно, какой это город — Кибирра Великая в Карин или Кибирра Малая в Памфилии[1253]. Впервые это морское соединение появляется в экспедиции против Карфагена в 698 г., когда друнгарий Кивирреотов упомянут в качестве командующего воинским контингентом из Корикоса. В то время Кивирреоты входили в состав флота Карависианов[1254].