Kimmerlerin, Frigya Hükümdarlığına son vermesinden sonra bölgeye sırasıyla Medler (M.Ö 585.) ve Persler (M.Ö. 547) hakim olmuştur. Persler, imparatorluklarını "satrap" olarak adlandırılan yöneticilerce yönetilen, yarı-bağımsız eyaletlere bölmüştür. Bu eyaletlerden biri olan Kapadokya bölgesinin adı "güzel cins atlar ülkesi" anlamına gelen Katpatuka idi.
Persler, sınırları içinde yaşayan insanlara istedikleri dini seçme ve kendi dillerini konuşma özgürlüğü sağlamıştır. Zoroaster dinine inan Persler içinse ateş kutsaldı ve bu sebepten Hasan Dağı ve Erciyes gibi volkanlar onlar için kutsal yerlerdi. Persler tarafından yapılan Kraliyet Yolu, Pers başkentini Kapadokya'ya, oradan da Ege'ye bağlamaktaydı. M.Ö. 334 ve 332 yıllarında iki kez yenilgiye uğratılan Pers imparatorluğu Büyük İskender tarafından fethedildi.
Pers imparatorluğuna son veren Büyük İskender Kapadokya'da büyük bir direnişle karşılaştı. Bölgeyi yönetimi altına almak isteyen Büyük İskender, komutanlarından Sabictus'u bu işle görevlendirdi fakat halk büyük bir direnç gösterdikten sonra, bir aristokrat olan Ariarhes'i Kral ilan etti. M.Ö. 332-322 yılları arasında hüküm süren Ariarthes I çok büyük başarılar elde ederek, Kapadokya Krallığının sınırlarını Karadeniz'e kadar genişletti.
M.S. 17'de Büyük İskender'in ölümüne kadar refah içinde yaşayan Kapadokya Krallığı, bir Roma eyaletine dönüştükten sonra Makedonyalılar,Galatlar ve Pontus Krallığı ile savaşlar yapmıştır.