خواجه از وى رميد و به مرو گريخت و به جغربيك داود بن ميكال سلجوقى پدر آلبارسلان پناهيد و از گذشته و كنون خود چيزى چند بر او خواند چندانكه در دل جغربيك سخنش افتاد و او را نزد فرزند خود آلبارسلان فرستاد و پيام كرد كه او را كاتب و مشار و از تدبير و مشورتش استفادت كن و خواجه نزد آلبارسلان زيست تا آنگاه كه آلبارسلان عميد الملك كندرى وزير را بكشت و وزارت را به خواجه سپرد و ازآنپس كه آلبارسلان در سال 465 درگذشت خواجه سلطان ملكشاه را به سلطنت برداشت و كار يكسره به دست خواجه افتاد و مدّت سى سال دوران وزارت خواجه طول كشيد ، ده سال در عصر آلبارسلان و بيست سال در روزگار ملكشاه و در اين مدّت از يك طرف به تدبير امور كشور پرداخت و از طرف ديگر مدرسه ساخت و مساجد بنيان نهاد و املاك بر آنها وقف كرد و مدرسهء نظاميّه بغداد از ساختمانهاى تاريخى اوست و خواجه مدرسهسازى را ابتكار كرد و با فقيهان و دانشمندان و صوفيان انس گرفت و مجلسش از فضلا پر بود و خود نيز مردى نيكوسيرت و نيكورفتار بود . گويند : « ميان او و تاج الملك ابو الغنائم موافقتى نبود و مانند همهء سروران كه رقيب يكديگرند بدخواه يكديگر بودند ، ازاينروى تاج الملك به ابن هباريّهء شاعر گفت چنين و چنانت دهم اگر خواجه را هجو كنى و بنكوهى ، ابن هباريّه گفت چگونه كسى را بنكوهم كه در خانهام هرچه بينم از كرم اوست .
گفت چاره نيست و ابن هباريّه اين ابيات گفت :
لا غرو ان ملك ابن * اسحاق و ساعده القدر
وصفت له الدنيا * و خص ابو الغنائم بالكدر
و الدهر كالدولاب * ليس يدور الا بالبقر
و به خواجه رسيد گفت : در شعر اخير به مثل مشهور اشارت كرده است كه مردم طوس گاوند و نظام الملك از همان گاوان و با اين وصف به روى ابن هباريّه نياورد » . امّا در پايان ميان او و سلطان ملكشاه را تركان خاتون تيره كرد چه خواجه ميل خاطرش به بر كياروق بود كه جانشين ملكشاه گردد و تركان خاتون هوايش در سلطنت فرزندش محمود بود و همين موضوع سبب قتل خواجه شد و به دست يكتن ديلمى به نام ابو طاهر كه در لباس تصوّف بود و در شمار فدائيان حسن صباح جراحت كاردى به دو رسيد و فرداى آن روز درگذشت و اين واقعه سال 485 نزديك نهاوند اتّفاق افتاد و جنازهء او را به اصفهان بردند و در آنجا به خاك سپردند .
گويند خواجه ازآنپس كه مجروح گرديد اين ابيات بگفت :
يكچند به اقبال تو اى شاه جهاندار * گرد ستم از چهرهء ايّام ستردم
طغراى نكونامى و منشور سعادت * پيش ملك العرش به توقيع تو بردم
آمد ز قضا مدّت عمرم نود و سه * وندر سفر از ضربت يك كارد بمردم
بگذاشتم آن خدمت ديرينه به فرزند * او را به خدا و به خداوند سپردم
و با اين وصف سلطان ملكشاه وزارت را به تاج الملك رقيب خواجه و وزير تركان خاتون بخشيد و خود نيز پس از هجده روز درگذشت و معزّى در اينباره گفت :
رفت در يك مه بفردوس برين دستور پير * شاه برنا از پى او رفت در ماه دگر
كرد ناگه قهر يزدان عجز سلطان آشكار * قهر يزدانى ببين و عجز سلطانى نگر