Urfalı Mathieu; Dünyanın sultanı, Hristiyanlar'ın hamisi ve babası olarak nitelendirdiği Melikşah'ın, sayısız bir orduyla Anadolu'ya gittiğini yazarken tüm Anadolu'yu değil sadece Bizans'a ait sayılan Antakya ve Urfa havalisini kastetmiştir. Böyle belirsiz ifadelere İslam kaynaklarında da rastlanıldığı halde Melikşah, doğu ve güney Anadolu'dan daha ileriye gitmemiştir. Bu rivayetlerin Süleyman Şah'ın ölümünden sonra İznik üzerine gönderilen Porsuk Bey'in veya Bozan Bey'in seferiyle karıştırıldığı muhakkaktır.
1086-1087'de Doğu Arabistan'da Lahsa'da yerleşmiş bulunan Karmatiler üzerine bir ordu göndermiştir. Kafkasya bölgesinde Melikşah'ın Gürcistan'a üç sefer yapmıştır. Bu seferlerden 1078-79 ve 1086'da yapılanlara Melikşah şahsen iştirak etmiştir. Bu seferler sonunda Gence'de idarede bulunan Emir İİİ. Fazıl, Gürcüler Kralı ve bölgedeki diğer mahalli hükümdarlar Büyük Selçuklu Devletinin hakimiyetini kabul ettiler. Güney-Doğu Anadolu'ya Diyarbakır'a yeni yerleşmiş olan Mervani Kürtleri buradan uzaklaştırmak için 1087'de veziri İbni Cahir'in hazırladığı planı uygulamaya başlamıştır. Sonra dikkatinin bu yörenin güneyine Musul ve Halep arasında bulunan ve "Ukeyl aşireti" Araplarının yerleşmiş olduğu bölgeye çekmiştir. 1086-87'de kışın yapılan bir sefere şahsen iştirak edip Urfa, Halep, Antakya ve Lazkiye'nin Selçuklular eline geçmesini sağlamış ve Büyük Selçuklu Devleti Doğu Akdeniz kıyılarına erişmiştir. Böylesine geniş sınırlara hükmeden Melikşah Vardan Areveltsi'nin aktarımına göre deniz kıyısından aldığı toprak ile babasının mezarını ziyaret etmiş, kumu mezarın üzerine serperek şu sözleri söylemiştir: "Müjde sana ey baba! Çünkü çocuk olarak bıraktığın evladın dünyayı baştan başa fethetti!"
Melikşah'ın bu çok geniş alanlarda askeri seferler ve fetihler yapabilmesine başlıca etken babası zamanında geliştirilip yetiştirilen ordusudur. Bu Selçuklu ordusu bir profesyonel ordu idi ve "gulam" adı verilen kölemenler ve paralı askerlerden oluşmaktaydı. Melikşah'ın devamlı olarak asgari 46 bin süvari askeri emri altında olduğu belirtilmiştir. Bu askerlerle komuta eden yetenekli emirleri de bulunmaktaydı. Melikşah'ın emirleri arasında Emir Savtekin (ö.1084), Emir Bozan (ö.1094), Emir Porsuk (ö.1099), Emir Aksungur (ö.1094), Emir Goharayın (ö.1100) ve Kumak sayılabilir. Melikşah ülkesinin batısında yürüttüğü fetih politikası Türkmen emirlere dayanmaktaydı. Örneğin Emir Artuk'u önce Filistin'e Atsız'a karşı sefere gönderdi; sonra Doğu Arabistan'da bulunan Karamatilere karşı seferde komutan yaptı. Yine Türkmen asıllı olan Emir Ahmed'i Gürcistan'a ilk seferde komutan yapmıştı ve sonra yine Türkmen asıllı Emir Yakup ve Emir İsaböri'yi Gürcistan seferlerine komutan olarak tayin etmiştir. Yemen'e gönderdiği ordunun komutanı'da Türkmen Emir Çabak idi. Bu Türkmen komutanların yol açtığı fetihler çok kere göçebe Türkmenler yeni yerleşecek araziler sağlamıştır. Örneğin Harran ve Diyarbakır ovalarına Türkmenler yerleşmiştir. Fakat Melikşah'ın Sultanlığı'nın başında Türkmenlerle arası iyi olmadığı iddia edilir. Buna örnek olarak 17 Nisan 1073'te amcası Kavurt Bey ile yaptığı "Karaç Muharebesi"'nde Türkmen emirlerinin muharebe içinde Melikşah ordusunu terk ettikleri gösterilir ve bu savaştan sonra da Melikşah'ın ülkesinin merkezinde bulunan İran'daki Cebal bölgesinde bulunan Türkmenleri zorla göç ettirip bu bölgeyi Türkmenlerden temizlediği de bu iddiaya ilave edilir.
Melikşah zamanında Büyük Selçuklu Devletinin sınırları Akdeniz ve Marmara Denizinden Kaşgar'a, Kafkasya'dan Yemen'e kadar uzanıyordu.
Melikşah askeri seferde olmadığı zamanlar İsfahan bölgesinde yaşamıştır. Bu nedenle İsfahan Melikşah döneminde Büyük Selçuklu Devleti'nin başkenti sayılmaktadır. Şahsi ve devlet hazinesi ile ordusunun kullanılmayan silahları İsfahan'dan 8 km güneyde Soffa Dağı zirvesinde bulunan bir dağ kalesi olan Dezkûh (veya Sāhdez)'de saklanmaktaydı. Saltanatını son dönemlerinde kendi kışlık ikametgahını ve kışlık devlet merkezini Bağdad'a taşıma kararı almıştı. Bu nedenle 1092'de büyük masraflar ve yatırımlar yaparak bu şehri imar ettirip devletin ilerigelenlerine de büyük ikametgahlar yaptırmıştı.
Melikşah'ın ülkesinin değişik kısımları aynı standartlara uyularak idare edilmemekteydi. Ülkenin merkezi bölgelerini ve stratejik önemi olan alanlarını (örneğin Bağdad, İsfahan, Nişabur, Harezm şehir ve bölgelerini) "sehna" adı verilen ordusunda başarı göstermiş olan gulam-kölemen asilli valilerle idare etmekteydi; örneğin Emir Atsız Harezm valisi, Emir Goherayin Bağdat valisi idi. Askeri fetihlerle eline geçirdiği kuzey Suriye ve Kafkaslarda da benzer idare uygulanmaktaydı. Emmir Savtekin Gence, Emir Yağı-Basan Antakya, Emir Aksungur Halep, Emir Bozan Urfa, Emir Çökermiş Musul valileri idiler. Buna benzer önemi olan yeni fetih edilmiş diğer bölgelere kendi Selçuklu sülalesinden gelen valiler tayin edilmekteydi ve bunlardan bazılarına "melik (kral)" unvanı verilmişti. Böylece Valvaley (günümüzde Kunduz Vilayeti) vadisine amcası Osman bin Çağrı; Tokaristan'a kardeşi Ayaz (ö. 1073); sonra oğlu Tekiş bin Ayaz (ö. 1084) daha sonra da onun oğlu Ahmet bin Tekiş; Herat'a kardeşi Boribars; Kerman'a (isyan çıkardığı için idam ettiği amcası Kavurt Bey'in oğulları) kuzenleri Sultanşah ve Turanşah; Azerbaycan'a kuzeni İsmail bin Yakuti bin Çağrı ve Suriye'ye kardeşi Tutuş vali olarak tayin edilmişlerdi.
Melikşah avlanmayı sever ve alimleri korurdu. Gazali, Kaşgarlı Mahmud ve Ömer Hayyam gibi alim ve şairleri himaye etti.
Bağdat'ta Sultan Melikşah Camiini yaptırdı. İsfahan'da bir rasathane, çeşitli yerlerde ise kervansaray, köprü, imaret, kale, hisar ve medreseler inşa ettirdi. Fakat Melikşah'ın yaptırdığı eserlerden hiçbiri günümüze kadar gelememiştir. İsfahan ve Nişabur'da onun adına yaptırılmış binalar için hazırlanamış kitabeler bulunmaktadır. 1074'te Celali takvimini hazırlattı. Bu takvim başkenti olan İsfahan'daki gözlemevinden yapılmış astronomik rasatlara bağlanmıştır.
Ticari mallardan alınan vergilerin bazılarını kaldırdı. Ermeni Patriğinin isteği üzerine kiliseleri, manastırları ve rahipleri vergiden muaf tuttu. Hac yollarında su kuyuları açtırdı ve bu yolların emniyetini sağladı.