Tuğrul Bey ve diğer Selçuklu hanedan mensupları toprak sahibi olunca, Oğuz boyları ve kabile reisleri yanlarına akın edip, toplandılar. Tuğrul Bey, çok güçlenip, bölgenin nüfûsu artınca; Gazneli Mes'ûd'a önceki üç şehrin dar geldiğini bildirip, 1037'de Merv, Serahs ve Baverd'iyi de istedi. Bu şehirlere karşılık da Gaznelilerin maaşlı askeri olma ve Horasan'daki asayişi temin etme taahhüdünde bulundular. Teklifleri oyalamaya alınınca, Tuğrul Bey küçük gruplar halinde akın harekatı yaptırdı. Çağrı Beyin idare ettiği akınlarda Selçuklular Cüzcan, Talekan ve Faryab'dan Rey'e kadar harekatta bulundular. Selçuklu akınlarını durdurmak için Gazneli Mes'ûd'un gönderdiği ordu Serahs yakınında 1038 Haziranında yenildi. Zafer sonrasında toplanan kurultayda Tuğrul Bey, hükümdar ilan edildi. Bu kurultay kararı ve 1038 tarihi Selçuklu Devletinin kuruluşu olarak kabul edilir.
Tuğrul Bey Nişapur'da kalıp, Çağrı Bey Merv'de melikler meliki olarak, askeri harekatları idare ederek ordu kumandanlığı yaptı. Tuğrul Beyin Nişapur'da istiklalini ilan etmesi, Gazne'de hoş karşılanmadı. Çağrı Bey, 1039 yılında Gaznelilerle iki kere muharebe yapıp, yenildi. Tuğrul Bey ve diğer Selçuklu hanedanları, Gazneli Mes'ûd'un düzenli ordusuna karşı gerilla harpleri yapıp, onları yıprattılar. Gazneli Mes'ûd, antlaşma istedi. Tuğrul Bey, Gaznelilerin türlü metodlarla Selçukluları Horasan'dan çıkarabileceklerini tahmin ederek, zaman kazanmak ve hazırlıkları tamamlamak için çöle çekildi. Sultan Gazneli Mes'ûd'un 1040 Baharındaki Tûs ve Serahs istikametindeki harekatı üzerine Selçuklular, Tuğrul Beye başvurup, harekete geçmesini istediler.
Tuğrul Bey, 1040 Mayısında çölden çıkıp, Serhas'ta Gazneli ordusuyla karşılaştı. Gazneliler ot ve yiyecek sıkıntısı çektiğinden Merv'e hareket edince, Tuğrul Beyin kumandasındaki Selçuklular, sağdan ve soldan taarruzla Haznelileri taciz ettiler. Dandanakan Kalesi önünde yapılan asıl muharebede Hazneliler bozuldular. 23 Mayıs 1040 tarihinde kazanılan Dandanakan Zaferiyle, Tuğrul Bey tekrar tahta oturdu. Tuğrul Bey zafer sonrasında ele geçen ganimetle zenginleşip, kumandanlara pekçok ihsanlarda bulundu. Kurultay toplandı. Kurultayda devletin temel stratejisi tespit edilip, planlar yapıldı. Bağdat'taki Abbasi Halifeliğine bağlılık ve hürmet ifade eden mektup gönderildi.
Çağrı Beyin 1060'ta vefatına kadar ortak iktidar sistemine göre hareket edilmesine rağmen, devleti temsil yetkisi Tuğrul Beye aitti. Tuğrul Bey hükümdarlığını ve Selçukluları maddi güçlerle kuvvetlendirdiği gibi manevi olarak da Halife, alim ve tasavvuf ehlinden destek alıyordu. Tebaasının refah seviyesini yükseltip, orduyu askera sisteme göre teşkilatlandırıyordu. 1040 Dandanakan Zaferi ve 1043'te devlet merkezini Rey'e taşıması sebebiyle Bağdat'taki Abbasi Halifesi El-Kaim'e tekrar bağlılığını arz etti. Tuğrul Beyin Abbasi Halifesiyle münasebeti Sünni İslam dünyasında büyük itibar kazanmasına sebep oldu. Halife El-Kaim, Tuğrul Beyin yanına; büyük İslam alimlerinden olup, sosyal ve devlet idaresi hakkında Ahkam-üs-Sultaniye isimli eserin sahibi olan Maverdi'yi gönderdi. Tuğrul Bey, ülkesinde hutbeyi Abbasi Halifesi adına okuttu; halifenin zalim Büveyhiler ve asilere karşı yardım talebini kabul etti. Halifeye bildirdiği arz; samimiyetinin ve temiz itikadının ifadesi olup, şunları ihtiva ediyordu: Halifeye hizmet etmek şerefine kavuşmak, Mekke'de Hac yapmak ve Hac yollarını Bedevilerin taarruzundan korumak, Suriye ve Mısır'da Fatimilerle harp etmektir. 1055'te Bağdat'a gelip, hutbede adı okundu.
