Обширное крепостное строительство завершилось в эпоху императора Юстиниана I (527–565 гг.), оно подробно описано Прокопием Кесарийским. Около 533 г. Юстиниан ввёл для Каппадокии новый принцип управления, сосредоточив в руках наместника-проконсула и гражданскую, и военную власть. Этот принцип спустя более ста лет стал основой фемной системы провинциального управления Византии. Реформы Юстиниана коснулись и территорий Восточной Каппадокии, где в 536 г. были созданы провинции Армения Первая, Вторая и Третья. Территориальное реформирование сопровождалось ростом императорских доменов. С 570 гг. на территории Каппадокии велись военные действия между Византией и Персией. В 575 г. персидский шах Хосров I совершил большой поход в Малую Азию, прошёл через Каппадокию, сжёг Севастию и Мелитину. С 577 г. комит Востока Маврикий (император в 582–602 гг.), выходец из Арависса в Восточной Каппадокии, возглавил войска в войне против персов и устроил ставку в Кесарии. Мирный договор, заключённый в 591 г. императором Маврикием и Хосровом, предусматривал новое деление Каппадокии. Провинция Армения Вторая со столицей в Мелитине стала Арменией Первой. Около 605 г., по сведениям Жития Феодора Сикеота, произошло вторжение в Каппадокию лазов совместно с цаннами. В ходе новой большой византийско-персидской войны к началу 610 гг. византийская оборона восточной границы рухнула. Согласно хроникам Феофана, Иоанна Зонары и Житию Феодора Сикеота, в 611 г. персы захватили Кесарию. После годичной осады город был отвоёван византийцами во главе с императором Ираклием. В 622 г. император Ираклий начал большую кампанию против персов и вступил, по словам хрониста Феофана, «в области фем», т.е. в Каппадокию. Походы Ираклия в 622–628 гг. завершились разгромом персов и заключением мира. Персы лишились всех завоёванных земель на Ближнем Востоке, в том числе Каппадокии. В 630 гг. началась война с арабами (см. Арабские завоевания), в которой были большие потери, и которая вызвала кризис в Византии. В 644 г. арабы, уже захватившие к этому времени Палестину, Сирию, Египет и Месопотамию, начали нападения на Малую Азию. В очередном походе на Аморий в 646–647 гг. они овладели Кесарией. Походы предпринимались ими в 654, 655 и 656 гг. В 659 г. император Констант II заключил мир с арабами, временно рейды с востока были остановлены. В это время византийцы впервые проводят кампании по переселению в Малую Азию ряда славянских племён с Балканского полуострова, где те обосновались с конца VI в. Славян расселили и в Каппадокии, вблизи перевала Киликийские Ворота, который следовало охранять. Сохранилась печать 694/695 г. с надписью: «Ипат пленных славян Первой и Второй Каппадокии». Но, по сообщению Феофана, многие славяне также стали жертвами новых арабских вторжений. В 665 г. 5 тыс. славян попали в плен и были переправлены в Сирию. В VII в. в Византии была введена и начала развиваться фемная организация, в которой объединялись функции гражданского и военного управления в руках главы фемы – стратилата или дуки.