Although the Paphlagonians play scarcely any part in history, they were one of the most ancient nations of Anatolia (Iliad, ii. 851-857). In the time of the Hittites, Paphlagonia was inhabited by the Kashka people, whose exact ethnic relation to the Paphlagonians is uncertain. It seems perhaps that they were related to the people of the adjoining country, Kappadokia, who were speakers of one of the Anatolian branch of the Indo-European languages. Their language would appear, from Strabo's testimony, to have been distinctive.
Paphlagonians were mentioned by Herodotos among the peoples conquered by Kroisos (Croesus), and they sent an important contingent to the army of Xerxes in 480 BC. Xenophon speaks of them as being governed by a prince of their own, without any reference to the neighboring satraps, a freedom perhaps due to the nature of their country, with its lofty mountain ranges and difficult passes. All these rulers appear to have borne the name Pylaimenes as a sign that they claimed descent from the chieftain of that name who figures in the Iliad as leader of the Paphlagonians.
At a later period, Paphlagonia passed under the control of the Makedonian kings, and after the death of Alexander the Great, it was assigned, together with Kappadokia and Mysia, to Eumenes. However, it continued to be governed by native princes until it was absorbed by the encroaching power of Pontos. The rulers of that dynasty became masters of the greater part of Paphlagonia as early as the reign of Mithradates I (302-266 BC), but it was not until 183 BC that Pharnakes reduced the Greek city of Sinope under their control. From that time, the whole province was incorporated into the kingdom of Pontos until the fall of Mithradates VI (65 BC).
Pompey united the coastal districts of Paphlagonia, along with the greater part of Pontos, with the Roman province of Bithynia, but left the interior of the country under the native princes, until the dynasty became extinct and the whole country was incorporated into the Roman Empire. The name was still retained by geographers, though its boundaries are not distinctly defined by the geographer Claudius Ptolemy. Paphlagonia reappeared as a separate province in the 5th century AD (Hierocles, Synecdemus c. 33). In the 7th century it became part of the theme of Opsikion, and later of the Bucellarian Theme, before being split off ca. 820 to form a separate province once again. [from Wikipedia].