Окончательный разгром павликиан в Малой Азии и решительная победа над арабами произошли только в 863 г. Память об этой победе отражена в византийском эпосе о Дигенисе Акрите. Несмотря на успехи византийцев, в начале правления императора Василия I Македонянина (867–886 гг.) павликианское движение было на подъёме. Его новый лидер Хрисохир претендовал на власть едва ли не над всей Малой Азией. Император Василий I отправился в поход и около 872 г. разбил павликиан, захватил Тефрику, а Хрисохир погиб в бою. До 879 г. византийская армия вела непрерывные военные действия на принадлежащих павликианам и арабам землях Каппадокии, укрепляя отвоёванные крепости и города, восстанавливая власть Византии. Походы против арабов император Василий I вёл с переменным успехом. При императоре Льве VI Мудром (886–912 гг.) арабы возобновили наступление и в 891 г. захватили Саланду, в 898 г. императорский Корон, на что византийцы ответили вторжением в Киликию около 900 г. В дальнейшем перевес сил всё более склонялся на сторону византийцев. Началась византийская «реконкиста» восточных территорий – новый период в истории Каппадокии. В первой трети X в. византийцы постепенно продвигались через Восточную Каппадокию к перевалам Тавра, Киликии и Северной Сирии. На отвоёванных территориях селились, прежде всего, армяне, император Лев VI устанавливал фемную систему. Восточная граница Византии отодвинулась на восток, в Армению, и только на юге и юго-востоке Каппадокия оставалась пограничной территорией. При императоре Романе I Лакапине (919–944 гг.), который был уроженцем селения на границе с Каппадокией, важным событием стало завоевание Мелитины в 934 г. войсками Иоанна Куркуаса. После этого граница империи приблизилась к рекам Тигр и Евфрат. Несмотря на продолжавшиеся столкновения на границе, положение Каппадокии существенно стабилизировалось. Император Никифор II Фока (963–969 гг.) захватил Мопсуестию и Тарс, полностью перенёс военные действия из Малой Азии в регионы к юго-востоку от неё. Впервые за 300 лет Каппадокия перестала быть пограничной областью. Для укрепления её хозяйственно-экономического положения в X в. проводились начатые ещё при Василии I в IX в. кампании по христианизации арабов, расселившихся в регионе, по привлечению сиро-яковитов на сторону Византии и переселению армян. Император Иоанн I Цимисхий (969–976 гг.) родился в близкой к Каппадокии феме Хозан, заселённой армянами. Каппадокия была вотчиной крупнейшего военно-аристократического клана Фок, поэтому в ответ на убийство Иоанном Цимисхием Никифора Фоки племянник последнего Варда Фока был провозглашён в Кесарии императором. Иоанн Цимисхий подавил восстание Фок, направив в Каппадокию войско во главе с Вардой Склиром. После смерти Иоанна Цимисхия в 976 г. в Каппадокии был поднят мятеж. Варда Склир, дука фемы Месопотамия, заключив союз с арабским эмиром, в Мелитине провозгласил себя императором. Мятеж охватил многие территории Малой Азии и был подавлен лишь в 979 г. В 987–989 гг. восстание против императора Василия II Болгаробойцы поднял Варда Фока, ставший к тому времени дукой Антиохии. После первых успехов, которыми он был обязан крепкому каппадокийскому тылу, он пал в битве. Таким образом, могущественные магнаты Каппадокии, имевшие такую власть в своих «вотчинных» землях, что изображали себя на фресках в местных храмах, представляли серьёзную опасность для Константинополя в X в. После походов императора Василия II в Сирию и Закавказье на рубеже X и XI вв. кавказские правители, ставшие вассалами Византии, и их подданные получили право и возможность переселяться на земли империи.