Единственный имевшийся в распоряжении Махмуда полководец Шир Мухаммад-хан находился в темнице по подозрению в государственной измене. Однако, не осмелившись покинуть столицу, Махмуд отправил Шир Мухаммада во главе войска кызылбашей навстречу мятежникам. Гильзаи были побеждены благодаря артиллерийскому обстрелу, но это поражение не было окончательным, и, получив подкрепления, они уклонились от сражения с армией Шир Мухаммада и, возможно, захватили бы столицу, если бы не останавливались, чтобы грабить деревни, находившиеся на их пути. Это дало Шир Мухаммаду время занять новую позицию для защиты Кабула, и на следующий день он разбил банды гильзаев, нанеся им тяжелые потери. Восстание было полностью подавлено лишь тогда, когда гильзаи были побеждены в четырех сражениях, последнее из которых, состоявшееся в мае 1802 г., было решающим.
В добавление к уже описанным успехам Махмуд победил узбеков неподалеку от Балха и изгнал их за Окс, а также нанес сокрушительное поражение племени хайбаров, которые снова восстали на стороне Шуджи уль-Мулька. Таким образом, его положение на троне было прочным, при этом его сын Камран-мирза владел Кандагаром, а Гератом управлял его брат хаджи Фируз уд-Дин.
Фанатики-афганцы всегда ненавидели кызылбашей, принадлежавших к шиитскому течению. Взбудораженный жалобами на дурное обращение с афганским юношей, почтенный главный мулла Мир Вайс вынес решение, санкционирующее истребление шиитов в Кабуле и обещающее радости рая тем, кто погибнет в борьбе. Два дня кызылбаши стойко защищались; Махмуд просто посылал сообщения, умоляя последователей муллы остановиться. Однако в конце концов Фатх-хан провозгласил себя сторонником кызылба-шей и, атаковав нападавших, положил конец беспорядкам. В то же время эти действия привели к тому, что несколько сердаров вступили в заговор против Махмуд-шаха и Фатх-хана.
Этот заговор против монарха возглавил Шир Мухаммад, который разгромил гильзаев, но ценные услуги которого не были в достаточной степени признаны. Понимая сложившееся положение, Махмуд-шах попытался схватить зачинщика, но Шир Мухаммад бежал в лагерь Шуджа уль-Мулька, в то время как главный мулла настроил горожан против Махмуда за поддержку еретиков-кызыл-башей. Махмуду и кызылбашам пришлось укрываться в крепости Бала-Хиссар, а Шуджа уль-Мульк разбил лагерь за пределами города, понимая, что его судьба зависит от исхода битвы, которая ему предстоит с войском Кандагара под командованием Фатх-хана, идущим на помощь к Махмуд-шаху. Когда два войска сошлись, Фатх-хан пошел в наступление, но его сторонники, поддавшиеся антикызылбашским настроениям, переметнулись к Шуджа уль-Мульку.
На следующий день победитель с триумфом въехал в Кабул. Сначала Махмуда приговорили к ослеплению, но этот приказ был отозван, и его бросили в подземную тюрьму, а Шуджа стал правителем Афганистана.
Шах Шуджа был обязан своим успехом Шир Мухаммаду, которого он назначил визирем, но которому он полностью не доверял. Первыми предпринятыми действиями была попытка завладеть Кандагаром. Находившийся там Фатх-хан устроил так, что Камран-мирза покинул город и укрылся в Герате. Сам сердар-баракзай остался в Кандагаре и выразил свою покорность шаху Шудже, но, очевидно, по совету Шир Мухаммада шах отнесся к нему холодно, и Фатх-хан удалился в свою крепость Гиришк. Тем самым шах Шуджа потерял поддержку могущественных баракзаев-сердаров.
Назначив сына своего слепого брата Кайсар-мирзу правителем Кандагара, шах Шуджа пошел на Пешавар во главе 30-тысячного войска с намерением утвердить свою власть в дальних провинциях Кашмир и Синд. Однако, узнав, что по наущению Фатх-хана Кайсар-мирза поднял восстание и стал претендентом на трон, он вернулся в Кандагар, победил своего племянника и снова двинулся на Пешавар, когда опять был вынужден возвратиться, так как Кайсар-мирза во второй раз занял Кандагар вместе с сердаром-баракзаем. На этот раз мятежник поклялся хранить верность Шудже и отречься от связей с Фатх-ханом, после чего вновь был назначен правителем Кандагара.
Правитель Герата Фируз уд-Дин поддался на подстрекательства влиятельного Фатх-хана и поднял мятеж, но мудро принял предложение шаха Шуджи стать правителем Герата на условиях полунезависимости. Свободный, как он думал, от забот о внутренних делах государства, шах Шуджа отправился в Синд и получил недоимки по дани. Затем он направился в Пешавар, куда и прибыл в апреле 1805 г.