El Tema de Paflagonia y su estratego es mencionado en por primera vez en noviembre de 826. El tema parece haber sido establecido sobre 820.[1][2] Su territorio correspondía aproximadamente a la antigua provinciatardía de Paflagonia, el cual había sido integrada en los temas de los opsicianos y bucelarios.[3][4] Su capital administrativa y eclesiástica, durante la antigüedad era Gangra.[5] Warren Treadgold – quién notablemente cree que Paflagonia había pertenecido al Tema armeniaco y no a los bucelarios – sugirió que su reaparición como provincia separada esta vinculada a la amenaza nueva naval del Rus en el mar Negro.[6] Según los geógrafos árabes Ibn Khordadbeh e Ibn al-Faqih, la provincia contaba con 5000 soldados y cinco fortalezas.[7] Una excepción notable a la jerarquía temática habitual era la existencia de un catapán a cargo de un escuadrón naval con base en Amastris.
Después de la Batalla de Manzikert en 1071 la mayoría de la región cayó en manos de los turcos selyúcidas. Las campañas de Juan II Comneno en la década de 1130 recuperaron la costa pero el interior quedó en manos turcas. Después de la cuarta cruzada, Paflagonia cayó bajo el control de David Comneno, pero en 1214 el emperador de NiceaTeodoro I Láscaris conquistó las partes occidentales hasta Amastris. Estas quedaron en manos bizantinas hasta finales del siglo XIV, cuándo fueron tomadas por turcos o el genoveses.
