11. yüzyılda Türkler akın akın Anadolu’ya yöneldiler. Malazgirt zaferinden önce Malatya 1057 yılında Türklerin eline geçti ise de Bizanslılar kenti geri aldılar. L. İsaakios Comnenos (1057-1059) döneminde Türkler Malatya’yı ele geçirip halkını tutsak ettiler. Kenti tekrar ele geçiren Konstantinos Ducas (1059-1067), (1060-61) yıllarında Malatya’nın sur ve hendeklerini yeniden yaptırdı. Ne var ki kent 1064 ve 1066’da kısa süreli de olsa Türklerin eline geçmesine engel olamadı. Ancak Kuşatma için gerekli silahları olmayan Türkler, düzenli Bizans ordularıyla başa çıkamayarak almış oldukları toprakları bırakıp, geriye çekilmek zorunda kalıyorlardı. Bu sırada Ortodoks Bizanslılarla Gragoryen Ermenileri arasındaki anlaşmazlık devam etmekteydi.
Bizanslılar 11. Yüzyılın başlarında Doğu Anadolu’yu istila ederek, buradaki Ermenileri Fırat yöresine sürdürmüşlerdi. Aynı yüzyılda başlayan Türk akınları yüzünden Ermeniler, güneybatıya doğru inip Malatya, Maraş ve Urfa bölgesinde toplandılar. Ermeniler kendilerine zorla Ortodoksluğu kabul ettirmeye çalışan Bizanslılara düşmandılar. Bu yüzden Anadolu’nun Türklere karşı savunulmasında Bizanslılara yardımcı olmadılar. 1071 yılında Bizans İmparatoru Romanos Diogenes (1068 – 1071), Türkleri Anadolu’dan atmak için büyük bir sefer düzenledi. Malazgirt’te savaş alanını topluca terk eden Ermeniler, Balkanlarda Bizans ordusuna dâhil edilen Uz ve Peçenek Türklerinin Alparslan saflarına geçmesiyle Bizanslıların büyük bir bozguna uğramalarına sebep oldular. Bu zaferle Bizanslıların son direnme güçlerini kıran Türkler, hızla Anadolu içlerine akmaya başladılar. Kendi aralarında başlayan saltanat kavgalarında Kutalmışoğlu Süleyman Şah kendilerine vilayetler verilmediği için isyan eden şehzadeler ve başka beylerde kendi boylarıyla Anadolu’da bir yurt tutmaya çalışıyorlardı. 1072 yılında Alparslan’ın ölümü üzerine oğlu Melikşah (1072 -1092) tahta geçti. Ama amcası Kavurd onun sultanlığını tanımadı. Kavurd’un başlattığı ayaklanmayı bastıramayacağını anlayan Melikşah, bu sırada Anadolu’nun fethiyle uğraşan Artuk Bey’i yardıma çağırdı. Artuk Bey, 1073 yılında Anadolu’dan Melikşah’a yardım etmek amacıyla ayrıldı. Bu arada saltanat iddiasıyla Alparslan’a karşı ayaklanmış olan Kutalmışoğullarından Süleyman Şah ile kardeşi Mansur Konya’dan İznik’e kadar olan bölgeyi ele geçirerek 1075 yılında merkezi İznik olmak üzere Anadolu Selçuklu Devleti’ni kurarak bağımsızlığını ilan etmişti. Akın akın gelen Türk göçlerinin Batı ve Orta Anadolu’da toplanmalarından yararlanan Ermeniler, doğuda birtakım prenslikler kurdular.
Bizanslıların Malatya-Antakya hattını Türklere karşı korumakla görevlendirdikleri Ermeni komutanı Filaretos, Malazgirt savaşından sonra kendi hesabına hareket etmeye başladı. Frank komutanı Raimbaut ve askerleri ile Toroslar’daki Ermeniler onun yönetimi altında birleştiler. Böylece güçlenen Filaretos, 1074 yılında Bizans İmparatoru 7. Michael Ducas’ın Antakya valiliğine atadığı komutan İzak’ı bozguna uğratmaya muvaffak oldu. Daha sonra Muş, Siirt yörelerinde Bizanslılara bağlı kalan Ermeni prensi Thornig ile çatışmaya girişti. Bu savaşlar sırasında Raimbaut öldü ise de Thornig’i saf dışı bırakmayı başardı. 1077 yılında Urfa’yı Bizans valisi Leon’un elinden aldığı gibi, Malatya’da yerleşen Ortodoks Ermeni Gabriel’i de kendisine bağladı. Selçuklulardan çekinen Filaretos, karısını Bağdat’a göndererek Melikşah’dan sağladığı bir fermanla Malatya’da hâkimiyetini perçinledi.
Fırat boylarında ortaya çıkan Ermeni Vasag’ı da 1079’da öldürten Filaretos, ardından Antakya’daki Rumları ortadan kaldırdı. Böylece; Malatya, Maraş Antakya ve Urfa yörelerini içine alan oldukça büyük bir prenslik kurdu. Bu sırada Anadolu Selçukluları giderek güçlenerek sınırlarını genişletmeye başlamışlardı. Bu durumdan kaygı duyan Filaretos, Büyük Selçuklu sultanı Melikşah ile kurmuş olduğu dostluğu devam etmekteydi. Süleyman Şah da, bu dostluğa karşı 1082 yılında doğu seferine çıkarak Kilikya yöresini kendisine bağladı. 1085 yılında Antakya seferine çıktığında Danişmendli Beyi Melik Danişmend Gazi, Malatya üzerine yürüdü, ama kenti alamadı. Filaretos, Melikşah’ın desteğini almak umuduyla Rey’e gitti. Bu gidişten bir sonuç elde edemedi ve kısa bir süre sonra Maraş’ta öldü. Süleyman Şah’ın 5 Haziran 1086 yılında Büyük Selçuklu Sultanı komutanlarından Tutuş tarafından öldürülmesi üzerine oğulları Kılıç Arslan ve Kulan Arslan’ın esir edilmeleri Anadolu Selçukluları’nı büyük bir sarsıntıya uğrattı. Süleyman Şah; bu sefere çıkarken yerine komutanlarından Ebu’l Kasım’ı bırakmıştı. Bu suretle devletin çökmesini engelledi. 1092 yılında Melikşah’ın ölümü üzerine İran’dan kaçan I. Kılıç Arslan İznik’e döndü. Onun yönetiminde Anadolu Selçukluları tekrar kısa sürede toparlandılar. Melik Danişmend Gazi ise Malatya’yı ele geçirmek için plan yapıyordu. I. Kılıç Arslan’ın kardeşi Kulan Arslan (Davud) Malatya’yı kuşattığında Melik Danişmend Gazi’nin de şehirde gözü olmasından dolayı oraya girerek Anadolu Selçukluları ile Ermeni Gabriel’i uzlaştırdı. Danişmendliler, Malatya üzerine saldırmak için uygun bir ortam beklerken, I. Kılıç Arslan 1095 yılında Malatya’yı Danişmendlilerden önce ele geçirmek için kuşatmayı yoğunlaştırdılar. Şehrin Ermeni ve Süryani halkı teslim olma yanlısı idi. I. Kılıç Arslan, bazı ayrıcalıklar tanıyacaklarına söz vererek Süryani patriğinin desteğini aldı ise de Gabriel onu öldürttü. Bunun üzerine, Anadolu Selçukluları kenti savaşla almaya karar verdiler. Bu sırada, I. Haçlı seferinin başlaması I. Kılıç Arslan’ın kuşatmadan vazgeçmesine sebep oldu. I. Haçlı seferi sarsıntısı geçtikten sonra, Anadolu Selçukluları ve Danişmendliler toparlandılar.
I. Kılıç Arslan Bizanslılarla uğraşırken, Melik Danişmend Gazi 1098 yılında Malatya üzerine yürüdü, şehir surlarının kuvvetli olması nedeniyle kuşatma uzun sürdü. Danişmendliler şehrin çevre ile bağlantısını keserek, üç yıl beklediler. Muhasaraya yaz aylarında devam edip, kışları tekrar Sivas’a dönüyorlardı. Uzun müddet dayanamayacağını anlayan Gabriel, Antakya Prensi Bohemond’a elçiler göndererek bir anlaşma sonunda, şehri ve güzelliği ile meşhur olan kızı Morfia’yı kendisine vermeyi teklif etti. Bunun üzerine Haçlılar hemen harekete geçtiler. Önce bunları sevinçle karşılayan Malatya’daki Ermeni Halk, Haçlıların yaptıkları yağma ve zulümler yüzünden, Danişmendlilerden yana olmaya başladı. Melik Danişmed Gazi, Ermenilerin yardımı ile Haçlıları Malatya önlerinde pusuya düşerek bozguna uğrattı. Başta ünlü Haçlı Kontu Bhomod ve Richard gibi Frank komutanları esir alındı. (1100). Niksar’da hapsedilen tutsakları kurtarmak için Avrupa’da yeni bir haçlı seferi düzenlendi. Bunun üzerine, Danişmendliler Malatya’yı kuşatmaktan vazgeçtiler.
Gabriel de Urfa kontu Bautounin’i Malatya’ya çağırarak himayesine girdi. 1101 yılında Anadolu’ya gelen Haçlı ordularını Anadolu Selçuklu ve Danişmendli kuvvetleri yok ettiler. Melik Danişmend Gazi, yeniden Malatya’yı kuşattı. Şehir kuşatılınca büyük bir kıtlık başladı. Gabriel ve Rumlar, Süryani ve Ermenilerden şüphelendikleri için, onlara zulüm ederek ve mallarına el koyarak birçoğunu da öldürdüler. Süryani halk Malatya Metropoliti Barsabuni’yi Gabriel’e gönderip, onu barışa yaklaştırmak istedi. Bunu kendisine karşı bir tertip zanneden Gabriel Bar Sabuni ile birlikte birçok ileri gelenleri öldürünce, askerler ve halk gazaba gelerek ihanete mecbur oldular. Şehrin kapılarını Danişmendlilere açarak askerlerin şehre girmesini sağladılar. Melik Danişment Gazi askerlerin şevkini arttırmak amacıyla, şehrin zenginliklerinden kendilerine pay verileceğini söyledi. Şehir alınınca ganimetler dağıtıldı. Bununla beraber kimseye dokunmayarak, halkın evlerine ve işlerine dönmelerini sağladı. Bundan başka ülkesinden buğday, öküz gibi zirai ihtiyaç maddeleri getirterek halka dağıttırdı. Zindanlarda bulunan insanları hürriyetine kavuşturdu. Gabriel ve ailesi, onun zulmüne uğrayan yerli Hıristiyanlar tarafından işkence ile öldürüldü. Malatya, Danişmend Gazi Ahmet zamanında bir saadet ve bolluk ülkesi oldu. Kılıç Arslan tarafından kuşatılan ancak, Haçlıların İznik’i kuşatmaları haberi üzerine bırakılan Malatya, artık Danişmend Gazi’nin fethi ile (18 Eylül 1101) Türk beldesi olmuş, daha sonra da Selçuklular ve Danişmendliler idaresinde kalmıştır. Anadolu Selçuklu Sultanı I. Kılıç Arslan, öteden beri almak istediği Malatya’nın Danişmendlilerin eline geçmesini iyi karşılamadı. Melik Danişmend Gazi, Niksar’da tutuklu Haçlı komutanlarını fidye karşılığında serbest bırakınca, Anadolu Selçukluları ile Danişmendlilerin arası açıldı. I. Kılıç Arslan 1103 yılında Danişmendliler üzerine yürüdü. Maraş yöresindeki savaşta I. Kılıç Arslan üstün geldi. Melik Danişmend Gazi’nin 1105 yılında ölümünden sonra Anadolu Selçukluları Malatya’yı kuşattılar. Kenti elinde tutan Melik Danişmend Gazi’nin oğlu Yağısıyan fazla dayanamayacağını anlayınca kenti Anadolu Selçukluları’na teslim etti.
Büyük Selçuklu Sultanı Mehmet Tapar (1105-1118), Anadolu Selçuklularının büyük ilerleyişini kaygı ile izliyordu. Musul, iki devlet arasında savaş çıkmasına sebep oldu. Büyük Selçuklu Sultanı, Musul valiliğini Çökermiş’in elinden alıp, Çavlı’ya vermişti. Çavlı, Çökermiş’i öldürünce Musul halkı onun çocuk yaştaki oğlu Zengi’yi vali yaptı. Çavlı Musul’u kuşattığında kent halkı, Malatya’da bulunan I.Kılıç Arslan’a haber göndererek yardım istedi. I. Kılıç Arslan, Çavlı’yı Nusaybin’de yendi ve Musul’a geldi. Kentin valiliğine oğlu Şahinşah’ı, komutanlığına da Bozumuş Bahadır’ı atadıktan sonra, yeni güçlerle Musul üzerine yürüyen Çavlı’yı karşılamaya hazırlandı. Savaşta Çavlı üstün geldi. I. Kılıç Arslan da öldürüldü. (1107) Musul’u alan Çavlı, Selçuklu şehzadesi Şahinşah’ı esir ederek İran’a götürdü. Bozumuş Bahadır, I. Kılıç Arslan’ın küçük oğlu Tuğrul Arslan’ı Malatya’ya getirerek Sultan ilan etti. Konya ve yöresinin yönetimini de Hasan Bey üstlendi. 1110 yılında İran’dan kaçan Şahinşah, Konya’ya gelerek tahta çıkıp Selçukluların yeniden toparlanmasını sağladı. 1115 yılında, Büyük Selçuklu Sultanı Mehmet Tapar, Porsuk komutasındaki bir orduyu Anadolu üzerine gönderdi. Artuklu beyi Necmeddin İl Gazi ve Malatya Sultanı Tuğrul Arslan ve Atabek’i Belek Porsuk’u yenerek geri çekilmeye zorladılar.
Bu arada Anadolu Selçukluları arasında taht kavgaları başlamıştı. Şahinşah’ın kardeşi Mesut, kayınbabası Danişmendli Emir Gazi Gümüştekin’in yardımıyla 1116 yılında, Anadolu Selçuklu tahtını ele geçirdi. Bu sırada, Artuklular ile Malatya Selçukluları, Franklara karşı savaşıyorlardı. Bunu fırsat bilen Mengücük beyi İshak (1118-1142) Malatya Sultanı Tuğrul Arslan’a ait Harput havalisine 1118 yılında bir akın yaptı. Bunun üzerine, 1119 yılında Tuğrul Arslan’ın Atabey’i olarak bu bölgeyi idare eden Belek, Mengücüklü beyliği üzerine yürüyerek Kemah bölgesini ele geçirdi. Trabzon Rum dukası Konstantin Gabras’ın yardımını sağlayan Mengücük beyi İshak geri döndüğünde, Tuğrul Arslan ve Atabeyi Belek, Danişmendli Emir Gazi Gümüştekin ile onlara karşı bir ittifak yaptılar. Gümüşhane’ye bağlı Şiran havalisinde (1120) yapılan savaşta Konstantin Gabras ile Mengücük beyi İshak yenilerek esir düştüler. Emir Gazi Gümüştekin esirleri, Tuğrul Arslan ve Belek’e danışmadan serbest bıraktığından, Danişmendliler ile Selçukluların arası açıldı. 1122 yılında Artuklu Beyi Necmeddin İl Gazi öldü. Yerine oğlu Hüsameddin Timurtaş geçti ise de ülkenin asıl yönetimi Malatya Sultanı Tuğrul beyin Atabeyi Belek’in elinde idi. Belek’in gücünden çekinen Danişmendli Emir Gazi Gümüştekin, Malatya Sultanı Tuğrul Arslan üzerine yürümeyi göze alamıyordu.
Ancak, Belek’in 1124 yılında ölümünden sonra, Danişmendli Emir Gazi Gümüştekin Anadolu Selçuklu sultanı I. Mesud ile Malatya üzerine yürüdü. Yöre bütünüyle işgal edildi ise de Malatya teslim olmadı. Gümüştekin oğlu Muhammed’e kuşatmaya devam etmesini söyleyerek geri döndü. Muhammed, Malatya yakınlarında Samanköy’e yerleşerek kenti altı ayın üzerinde kuşatma altında tuttu. Malatya’da kıtlık baş göstermesi üzerine, Tuğrul Arslan Haçlılardan yardım istedi. Bu sırada Halep’i almaya çalışan Haçlılar, yardımda geç kaldılar. Tuğrul Arslan annesini de yanına alarak Minşar kalesine çekildi. Malatya’yı, yöreye gelmiş olan Gümüştekin’e teslim etti. (1124) Anadolu Selçuklu Sultanı I. Mesud, kardeşi Tuğrul Arslan’ı böylece saf dışı bıraktıktan sonra Malatya’yı Emir Gazi’ye terk etti. Ancak, Ankara, Kastamonu yörelerine hâkim olan kardeşi Melik Arap, babasına ait olan beldenin Danişmendlilere verilmesine kızdı ya da bunu bahane ederek topladığı kuvveti ile 1126 yılında I. Mesud’un üzerine yürüdü. Emir Gazi Gümüştekin, o sırada Artuklularla uğraştığından, Sultan I. Mesud yenildi. Bizans İmparatoru II. Yuannis Komnenos’dan yardım alarak geri dönen I. Mesud kayınbabası Emir Gazi Gümüştekin ile birleşip Melik Arap üzerine yürüyerek onu yendiler. Böylece Anadolu Selçuklu taht kavgaları sona ermiş oldu. 1134 yılında Danişmend Gazi Gümüştekin öldüğünde, tahta büyük oğlu Melik Muhammed geçti ise de, kardeşleri Ayn Ud Devle ile Yağan onun sultanlığını tanımadılar. Melik Muhammed 1135 yılında Yağan’ı öldürttü, Ayn Ud Devle Malatya’ya kaçtı fakat burada tutunamadı. Melik Muhammed, 1143 yılında öldüğünde, Zunnun, Yunus ve İbrahim adlarındaki oğulları arasında taht kavgaları çıktı. Bu kavgalara Belik Muhammed’in kardeşleri Yağıbasan ile Ayn Ud Devle de karıştılar. Daha önce Malatya’dan ayrılmak zorunda kalan oğlu Ayn Ud Devle, Minsar kalesi beyi Yunus ile birleşerek geri döndü.
Kent halkı kendisini hükümdar olarak tanıdı. I. Mesud ise Zunnun’u destekliyordu. Sultan I. Mesud, Yağıbasan’ı yendikten sonra 1143’te Malatya’yı kuşattı. Kuşatma, Bizanslıların saldırıya geçmesi üzerine kaldırıldı. 1144 yılında, şehri ikinci defa kuşatan I. Mesud, Bizans İmparatoru I. Manuel Komnenos’un saldırması üzerine kenti yine alamadı. Ayn Ud Devle 1152 yılında ölünce yerine çocuk yaştaki oğlu Zulkarneyn geçti. Sivas’ta hüküm süren Yağıbasan, Zulkarneyn ile I. Mesud’a karşı ittifak yaptılar. Selçukluların Sivas’a yürümesi üzerine, bağışlanması için ricada bulundu. Yağıbasan’ı böylece saf dışı bırakan I. Mesud, Malatya üzerine yürüdü, direnemeyeceğini anlayan Zulkarney, Selçuklu egemenliğini tanıdı. 1155 yılında I. Mesud ölünce, yerine oğlu II. Kılıç Arslan geçti. Sivas Emiri Yağıbasan, Kayseri Emiri Zunnun ile Malatya Emiri Zulkarneyn, onun sultanlığını tanımadılar. Selçuklu tahtına, Ankara-Çankırı emiri Şahinşah’ı geçirmek için ayaklanan ittifak güçlerine yenilen II. Kılıç Arslan, yardım almak umuduyla Bizanslılara sığında (1162) Bizanslılardan aldığı yardımla geri dönen II. Kılıç Arslan Artuklu Kara Arslan, Mardin Emiri Necmeddin Alp’i, Dilmaçoğlu beyi Fahrettin Devlet Şah da ona katıldılar. II. Kılıç Arslan batıdan öbürleri doğudan saldırıya geçince, Yağıbasan kaçmak zorunda kaldı. (1163) II. Kılıç Arslan, bundan sonra Malatya’yı ele geçirmeye çalıştı. Malatya Emiri Zulkarneyn (1162) de ölmüş, yerine oğlu Melik Nesrettin Muhammed geçmişti. Ancak kardeşi Feridun onu tahttan indirdi. Nasrettin Muhammed de II. Kılıç Arslan’a sığındı.
Anadolu Selçukluları bu karışık ortamdan yararlanarak 1171 yılında Malatya’yı kuşattılar. Fazla direnemeyeceğini anlayan Ferudun kentten ayrılarak, II. Kılıç Arslan’ın rakibi atabey Nureddin Mahmut’un yanına sığındı. Nureddin Mahmud, Anadolu Selçuklularına karşı savaşa hazırlandığından, 2. Kılıç Arslan kuşatmadan vazgeçti. Malatya yöresinden 12.000 kişiyi sürgün ederek Kayseri’ye döndü. Nureddin Mahmut 1174 yılında ölünce, Anadolu Selçuklularının yanında bulunan Melik Nesreddin Muhammed gizlice Malatya’ya girdi. Kardeşi Feridun’u öldürdükten sonra kente hâkim oldu. (15 Şubat 1175) Öteden beri Malatya’yı almak isteyen Anadolu Selçukluları 1178 yılında kenti kuşatınca Nasreddin Muhammed Harput’a kaçtı ve Malatya Anadolu Selçuklularının eline geçti. II. Kılıç Arslan (1186) yılında ülkesini, yaşlandığı için sağlığında on bir oğlu arasında paylaştırdı. Malatya, Muizeddin Kayserşah’ın payına düştü. Kısa bir süre sonra kardeşler arasında taht kavgaları başladı. Sivas Emiri Kutbeddin Melikşah, Konya’yı ele geçirip kendisini veliaht ilan ettirdi ve öbür kardeşlerini saf dışı bırakmaya çalıştı. Baskıdan bıkan Malatya Emiri Muizeddin Kayserşah, 1191 yılında Selahaddin Eyyubi’ye sığındı. Onun desteğini sağladıktan sonra Malatya’ya dönebildi. Kutbeddin Melikşah bu defa Kayseri Emiri Nureddin Sultanşah’ı saf dışı etmeye karar vermiş, II. Kılıç Arslan’ı da kendisine katılmaya zorlamıştı. Kayseri’nin kuşatılması sırasında, Kutbeddin Melikşah’ın baskılarından bıkan II. Kılıç Arslan Nureddin Sultan Şah’ın yanına kaçtı. Bunun üzerine Kutbeddin Melikşah geri dönerek Konya’da Sultanlığını ilan etti. II. Kılıç Arslan, Nureddin Sultan Şah’ın saltanat hırsı ile yaptığı baskılar yüzünden, Uluborlu Emiri Gıyaseddin Keyhüsrev’in yanına gitti. Onu kendisine veliaht yaparak Konya’yı ele geçirdi. II. Kılıç Arslan, 1192 yılında öldüğünde yerine I. Gıyaseddin Keyhüsrev geçti. Ancak, 1196 yılında Konya’yı alan Tokat emiri Süleyman Şah, Anadolu Tahtına çıktı. I. Gıyaseddin Keyhüsrev’de Bizanslılardan yardım almak için İstanbul’a gitti. II. Süleyman Şah, ülkede birliği sağlamaya çalıştı. 1200 yılında Malatya’yı ele geçirdi. Malatya Emiri Muizeddin Kayserşah, Eyyubilere sığınmak zorunda kaldı.1205 yılında, II. Süleymanşah öldüğünde yerine çocuk yaştaki oğlu III. İzzettin Kılıç Arslan geçti. 1196 yılında tahtı II. Süleymanşah’a kaptıran I. Gıyaseddin Keyhüsrev geri dönerek Konya’yı geri aldı ve sultanlığını ilan etti. Oğullarından İzzettin Keykavus’u Malatya’ya, Alâeddin Keykubat’ı Tokat’a, Celaleddin Keyferudun’u Koyulhisar’a Emir olarak atadı. Gıyaseddin’in 1211 yılında ölümünden sonra yerine büyük oğlu Malatya emiri İzzettin Keykavus geçti. Kardeşi Alaaddin Keykubat onun Sultanlığını tanımayarak ayaklandı, sonuçta yenildi. Malatya civarında bulunan Masara (Minşar) ve bilahare de Kezirpert(Gaderbeyt) Kalesine hapsedildi. I. İzzettin Keykavus’un 1220 yılında ölümünden sonra yerine I. Alaaddin Keykubat geçirildi. Keykubat, Malatya şehir surlarını onartarak, kentin savunmasını güçlendirdi. Şehri imar eden Keykubat’ın en önemli eserlerinden biri de 1224 yılında yapılan ve Anadolu Büyük Selçuklu Mimari geleneğini temsil eden tek eser Malatya Ulu Camii (Eski Malatya – Battalgazi) dir.
Keykubat, Fırat boylarında 1226 yılında yeni fetihlere girişti.
Adıyaman, Kâhta ve Çemişgezek kaleleri Sultana tabi olmuştur. Kış yaklaştığında, Malatya’dan ayrılarak Antalya’ya hareket etmiştir. Alaaddin Keykubat yerine İzzettin Kılıç Arslan’ın geçmesini istiyordu. Ancak, 1237 yılında öldüğünde dönemin veziri Sadettin Köpek, hile ile II. Gıyaseddin Keyhüsrev’i başa geçirdi. Anadolu Selçukluları’nın hizmetinde bulunan Harzemşah’lı beyler, bu durumu kabullenmediler. II. Gıyaseddin, Harzem Beylerinin ve askerlerinin başında bulunan Kayırhan’ı hapsettirdi. Kayırhan’ın hapiste ölümü üzerine Harzemşahlılar, batı ve orta Anadoluyu terk ederek, Malatya’ya doğru hareket ettiler. Masara veya Arapgir yolundan Fırat nehrini geçtiler, yol üzerinde bulunan bütün vilayetleri yağma ettiler. Bu durumda telaşa düşen II. Gıyaseddin Keyhüsrev, Kemalettin Kamyar’ı merkez ordusunun komutanlığına tayin edip, Harzemleri geri döndürmek maksadıyla gönderdi. Kemalettin Kamyar Malatya’ya geldiğinde dönemin Subaşısı olan Seyf Üd Devle Er Tokoş’u onları takiben Harput’a yolladı. O da Harput Subaşısı Seyfettin Bayram ile birlikte Harzemlilerinde anlaşmaya yanaşmamaları sonucu savaş başladı. Onlar Seyfeddin Bayram’ı bazı askerleri ile öldürdüler, Seyf Üd Devle Er Tokuş’u da esir ettiler. Yöre büyük zararlar gördü. Moğol istilasının yaklaştığı sırada Harzemşahları kaybetmek, devletin direnme gücünü büyük ölçüde azalttı. 1240 yılında Baba İshak’ın emri üzerine Türkmenler, sığır, koyun ve diğer mallarını satıp silah satın aldılar; cihad ilanı Türk kabile ve obaları arasında yayılınca, Türkmenler her köşeden karıncalar gibi İsyana başladılar, kısa sürede bu isyan büyüyüp genişledi. Malatya Subaşısı Muzaffereddin Alişir, ayaklanmayı bastırmaya çalıştıysa da büyük kayıplar vererek bozguna uğradı. Malatya’ya dönen Muzaffereddin Alişir, yeniden asker toplayarak ayaklananların üzerlerine yürüdü, fakat yenilerek geri çekilmek zorunda kaldı. Devlet bu ayaklanmayı güçlükle önleyebildi. Selçukluların bu durumunu gören Moğollar, kararsızlıklaından sıyrılıp, Anadolu’ya saldırıya geçtiler. 1243 yılındaki Kösedağ Savaşında Selçuklular yenilgiye uğrayınca, Sultan II. Gıyaseddin Keyhüsrev, Tokat’a kaçtı. Kösedağ bozgunu üzerine, Malatya subaşısı Reşideddin, yanına adamlarını ve değerli eşyalarını alarak Malatya’yı terk etti. Yöneticisiz kalan Malatya’da Müslüman ve Hıristiyan halk, anlaşıp kent surlarına ve kapılarına muhafızlar görevlendirerek Malatya’yı dış saldırılardan korudular. Ancak, Moğol istilası ürünlerin toplanmasına engel olmakta idi. Moğollarla anlaşma yapıldı ve kentin subaşısı Reşideddin geri döndü. Bu sırada Yasavur Noyan komutasındaki bir Moğol ordusu, Halep’ten sonra Malatya önlerine geldi. Moğollar surların dışında kalan halkı öldürüp, ürünleri yaktılar. Subaşı Reşideddin, kent halkından 40.000 altın toplayarak Moğollara verdi ve onların Azerbaycan’a dönmelerini sağladı. Moğolların ayrılmalarından sonra Malatya’da kıtlıkla birlikte veba salgını baş gösterdi. 1256 yılında Baycu Noyan, Anadolu seferine çıktı. II. İzzettin Keykavus’un Bizanslılara sığınması üzerine, 4. Kılıç Arslan Anadolu Selçuklu tahtında rakipsiz kaldı. 1257 yılında Baycu Noyan’ın Azerbaycan’a gitmesinden sonra geri dönen II. İzzettin Keykavus tahtı ele geçirdi. II. İzzetttin Keykavus, Şerafettin Ahmed’i Malatya’ya gönderdi. Moğollara yenilmesi üzerine yerine, cüssesi küçük zekâsı ve cesareti yüksek Ali Bahadır’ı Malatya’ya gönderdi. Büyük bir kıtlık geçiren ve buğdayın bir yükü 120 dirheme satılan Malatya’da halk Ali Bahadır’ı iyi karşılayarak, Sultan İzzettin’in hâkimiyetini kabul ettiler. Onun otoritesi ile yollar açıldı ve kıtlığa son verildi. Ancak, Baycu Noyan, Malatya üzerine yürüyünce, Ali Bahadır Kâhta’ya kaçtı. Baycu Malatyalılara Kılıç Arslan’ın saltanatını tanımaları için yemin ettirdi ve şehrin altınlarını toplayarak, Bağdat muharasına giderken, Kılıç Arslan’ın emirlerinden Fahrettin Ayaz’ı Malatya valiliğine tayin etti.
Baycu, 1258 yılında Anadolu’dan ayrılınca, Ali Bahadır Malatya önlerine geldi. Ettikleri yemine bağlı kalan Malatya halkı, Moğol istilasından da korktuğu için kentin kapılarını kapalı tuttular. Ancak, baş gösteren açlık yüzünden açmak zorunda kaldılar. Ali Bahadır, Kılıç Arslan yanlısı Fahrettin Ayaz ile iğdiş başı Muin’i öldürttü. Ali Bahadır Moğollar’ın ilerlediğini öğrenince Malatya’yı terk edip, Sultan İzzettin’in yanına döndü. Ülke karışıklıklar içinde bunalmıştı. Moğol baskısı giderek artıyor, Anadolu’daki Türkmen boyları da fırsat buldukça ayaklanıyorlardı. İlhanlı hanı, Olcayto, Anadolu üzerindeki İlhanlı egemenliğinin çökmekte olduğunu görünce 1314 yılında Emir Çoban’ı Naib tayin eylemişti. Olcayto için Haraç toplayan Mardu ve Cemaleddin, Malatya halkına sürekli baskı uyguladılar. Tecavüze uğrayan Malatyalılar bu mülkün 170 yıldan beri kendilerine ait olduğunu, Selçuklu sultanlarının verdiği beratların ellerinde bulunduğunu söyleyerek acı acı yakınıyorlardı.
Halep Memlük Emiri Seyfettin Tengiz, ordu ile Malatya’ya varınca Cemalettin Hızır, kentin ileri gelenleri ile birlikte onu karşıladı ve bağışlanmaları dileğinde bulundular. Seyfettin Tengiz tarafından affedilen Malatya halkı askerlerin şehri yağmalamalarına müsaade etmemek kapıya bırakılan muhafızları dinlemeyerek şehre girdiler. Selçuklular devrinde Malatya, sanayi ve ticareti ileri, zengin bir şehirdi. Burada kumaş dokuyan tezgâh miktarı 12.000 ile 19.000 arasındaydı. İşte Memlük askerleri bu zengin şehri yağmalamaya başladılar. Müslüman- Hıristiyan farkı gözetmeksizin kıymetli eşyalarını alarak, halkını esir ettiler. Bununla beraber dönüşte Müslüman esirleri serbest bıraktılar. Memlükler kentten ayrıldıktan sonra Emir Çoban, Malatya’ya gelip düzeni sağladı. Yakılıp yıkılan yapıların onarılmasını emretti. Malatya’nın müdafaası için de 2000 süvari bıraktıktan sonra, 1315’te Tebriz’e döndü. 1318 tarihinde sonra da Anadolu Selçuklu Devleti tarihe karıştı.