Заселение Каппадокии выходцами из Армении достигло пика в 1020 гг. В середине XI в. на восточных границах Византии возникла новая опасность – племена тюрок-сельджуков, которые мигрировали из регионов Центральной Азии на запад. Уже в 1048 г. они впервые вторглись в земли византийской Армении, а в 1064–1065 гг. захватили Ани, затем разорили Грузию. В условиях этой нарастающей угрозы войска в Каппадокии под командованием Никифора Вриенния в 1057 г. поддержали мятеж Исаака Комнина против императора Михаила VI Стратиотика и возвели его на престол. В 1059 г. сельджуки вторглись в Каппадокию и сопредельные с ней районы, разграбили Севастию. В период правления императора Константина X Дуки (1059–1067 гг.) они продолжали наступление, вновь превратив Каппадокию и большую часть центральных областей Малой Азии в приграничные, опустошаемые войной земли. Император Роман IV Диоген (1068–1071 гг.), каппадокиец по происхождению, попытался создать заслон сельджукскому натиску, объединив все силы империи, в том числе македонян, каппадокийцев, узов, франков, варягов, аланов, армян, болгар, хазар, немцев, франков, грузин, печенегов, русских, сирийцев, тюрок. Походы Романа IV в течение нескольких лет проходили с неизменным успехом, никак, однако, не решая сельджукской проблемы. Напротив, сельджуки во главе с султаном Алп-Арсланом к 1070 г. наносили всё более чувствительные удары по городам Малой Азии, доходя до Хон (Колосс) на западе полуострова. Византийцы собрали все силы для генерального сражения и встретились с сельджуками у Манцикерта, к северу от озера Ван, 19 (или 26) августа 1071 г. Битва, начавшаяся удачно для византийцев, на второй день окончилась их разгромом. Современники, описавшие эти события, в качестве одной из причин поражения называли дезертирство подразделения каппадокийцев. Роман IV был пленён и был вынужден подписать мирный договор, оставлявший сельджукам Каппадокию и ряд других областей в Малой Азии; за большой выкуп он был отпущен из плена. В это время в Константинополе власть захватил Михаил VII Дука. Роман IV хотел остаться в Каппадокии, постригся в монахи, но, настигнутый эмиссарами Михаила VII Дуки, был ослеплён и вскоре умер. Сельджуки в течение нескольких лет занимали значительную часть Малой Азии и всю Каппадокию. Хотя Византийская империя просуществовала ещё почти 400 лет, земли Каппадокии больше никогда не входили в её состав. Формально последнее упоминание провинции Каппадокия в византийских источниках относится к 1081 г., когда император Алексей I Комнин призвал в Константинополь в числе других чиновников «топарха Каппадокии и Хомы». Однако, скорее, здесь, по мнению исследователей, под Каппадокией имеются в виду области Галатии и Ликаонии, бывшие при Льве VI частью собственно Каппадокии. В 1085 г. Каппадокия вошла в состав северной части новообразованного тюркского султаната Данишмандидов. В 1097 г. участники первого Крестового похода прошли через Каппадокию, двигаясь с северо-запада на юго-восток, на Антиохию, не задерживаясь в Кесарии, которая в то время лежала в руинах. В Ираклии Танкред и Балдуин Булонский отделились от основных сил под командованием Боэмунда Тарентского, стремясь захватить владения в Киликии. Крестоносное же войско Боэмунда и Раймунда Тулузского проследовало далее, не задерживаясь надолго в Кесарии. Отдельные территории Каппадокии некоторое время не были подчинены сельджукам. Так, Мелитина оказалась под властью армянского правителя («игемона») Гавриила, православного халкидонита по вероисповеданию. Гавриил погиб в 1103 г. при защите города от сельджуков. К 1111 г. сельджуки уничтожили остатки византийских войск на территории своего султаната, в который вошла вся Каппадокия, кроме принадлежавших Киликийской Армении отдельных крепостей на северных склонах Тавра на периферии Каппадокии.