Herodotoksen mukaan Kroisos valtasi Paflagonian ja myöhemmin sen valtasi Persian valtakunta. Vuonna 480 eaa. paflagonialaiset lähettivät joukkoja Kserkses I:n sotaretkelle Kreikkaan. Ksenofonin mukaan Paflagoniaa hallitsi oma ruhtinas eikä se ollut suoraan minkään satraapin alainen. Aleksanteri Suuren valloitusten jälkeen diadokit jakoivat valtakunnan keskenään ja Paflagonia joutui Myysian ja Kappadokian kanssa Eumeneelle. Paflagonia pysyi kuitenkin miltei itsenäisenä siihen asti kun Pontoksen hallitsijat valtasivat sen 200-luvulla eaa. Paflagonia pysyi Pontoksen vallassa aina Mithridates VI:n kukistumiseen vuonna 65 eaa.
Pompeius yhdisti Paflagonian Roomalaiseen Bithynian provinssiin. Paflagonialaiset ruhtinaat jatkoivat kuitenkin alueen sisäosien hallitsemista vielä jonkin aikaa. Pompeius perusti Paflagoniaan kaupungin nimellä Pompeiopolis.