В 713 году Кутайба выстроил большую мечеть на месте храма огня. Новая вера открыто утверждалась в старом центре власти. Труднее было собрать верующих. Местным жителям платили по два дирхема в качестве стимула за посещение пятничной молитвы. Поскольку они не знали, как выполняются молитвенные обряды, пришлось назначать специальных людей, которые по-персидски указывали, когда кланяться, а когда простираться ниц. Коран читали по-персидски, потому что арабского народ не знал. Не всех жителей города привлекала новая вера. Рассказывали, что бедняков соблазняла награда в два дирхема, но богатые упрямо отсиживались в загородных домах. Однажды в пятницу мусульмане пошли по этим домам, приглашая их обитателей на молитву. Их встретили градом камней. Тогда мусульмане набросились на дома. Желая унизить хозяев, они поснимали двери и унесли их с собой, чтобы приладить к новой мечети. На этих дверях были изображения домашних богов, и, принеся двери к мечети, изображения с них соскребли — то ли потому, что ислам возбранял изображения живых существ, то ли просто в насмешку над старой верой и ее приверженцами. Много лет спустя Наршаки, местный бухарский историк, заметил на дверях следы стертых изображений и спросил, откуда они. Таким образом эта история дошла до нас.
Кроме того, Кутайба установил место праздничных молитв у подножия цитадели на регистане (площади). Мусульманам, когда они первые собрались помолиться здесь, велено было захватить с собой оружие, «потому что ислам был еще внове и мусульманам грозила опасность от неверных»
Несмотря на перемены в ритуалах, религии и церемониях, за царем Бухары оставалась значительная власть над городом и окружающим оазисом, и старая граница продержалась эпоху халифатов Омейядов и Аббасидов, пока в конце IX века к власти не пришли Саманиды. Как и во многих областях Трансоксании, правление мусульман здесь было, в сущности, протекторатом, и арабские власти правили совместно или через посредство местной аристократии. Успехи арабов заставили царя Согдианы Тархуна покинуть свою столицу Самарканд и явиться искать мира. Он пришел к лагерю Кутайбы всего с двумя людьми и, оставаясь на другом берегу реки Бухары, открыл переговоры. Он согласился платить дань в обмен на гарантию, что арабского вторжения не будет.
Если Кутайба, вернувшись в Мерв после первого завоевания Бухары осенью 709 года, был доволен своими успехами, то его благодушное настроение было грубо нарушено. Хан Найзак, прибывший в Мерв и участвовавший в экспедиции на Бухару, по-видимому, решил, что, если он хочет возвратить себе независимость, надо действовать, пока не поздно. «Я с этим человеком, — сказал он якобы своей свите, — и с ним я не чувствую себя в безопасности. Араб — как пес: если его бьешь, он лает, а если кормишь — виляет хвостом. Если ты сражался с ним, а затем дал ему что-то, он доволен и забывает о том, что ты делал раньше. Тархун несколько раз сражался с ним, но вот он принес дань, и ее приняли, и довольны им. Он несдержан и полон собой». Очевидно, из этого следовало, что Найзак может попытаться поднять восстание, а если оно не удастся, сможет снова помириться с Кутайбой. Когда армия подошла к Амулю на правом берегу Окса. Найзак попросил разрешения вернуться в родные места и получил его.
Он со всей поспешностью устремился в Балх. Несомненно, он планировал взбунтовать всех князей Тохаристана в среднем течении Окса против власти арабов. Добравшись до города, он первым делом принес молитвы в буддийском храме Нава Бихара, прося об успехе в предстоящей борьбе. Он понимал, что Кутайба скоро пожалеет, что отпустил его, и прикажет местным арабским градоправителям задержать беглеца, поэтому он нигде не задерживался надолго. Он написал письма с призывами подержать его к целому списку местных князей: испахбаду из Балха, Бадаму из Мервруда, Шураку из Таликана, Тусику из Фарьяба и правителю Джаузджана. Все ответили согласием, и он назначил им встречу весной 710 года. Сделал он и приготовления на случай, если дела обернутся против него. Он написал шаху далекого Кабула, расположенного далеко за пределами досягаемости арабских армий, с просьбой о помощи. Найзак отослал на хранение в Кабул большую часть своего имущества и получил заверение, что в случае необходимости шах примет его. Затем он изгнал ставленника Кутайбы и стал ждать весны и сбора союзников. Он сделал все что мог, но недооценил противника.
Кутайба в это время находился на зимних квартирах в Мерве, а его воины большей частью разошлись по домам, однако он сразу отправил в Балх 1200 человек под командой своего брата с приказом продержаться там до весны. В самом начале следующего, 710 года, прежде чем мятежники успели мобилизоваться, он собрал армию в Мерве и арабских поселениях Хорасана и выдвинулся в Тохаристан. Первой остановкой на его пути был Мервруд, городишко в верхнем течении реки Мургаб. Его правитель обещал поддержать Найзака. Сам правитель бежал, но Кутайба захватил двух его сыновей и казнил их. Следующим был Ткликан, где, по некоторым сведениям, он убил и распял множество людей с целью запугать местных жителей. После этого царь Фарьяба смиренно выказал покорность, и его народ пощадили. Его при-меру почти сразу последовал царь Джаузджана, и далее Кутайба принимал покорность народов на всем пути к Балху.
Найзак видел, что его план рушится. Быстрые и решительные действия Кутайбы подрезали ему крылья, и почти все князья, бывшие его союзниками, уже примирились с Кутайбой. Всеми городами Тохаристана правили арабские ставленники. Тогда он бежал на юг к Гиндукушу в надежде добраться до Кабула. Он оставил часть своих сторонников в Хульме (ныне Ташкурган). Tам дорога на юг уходила из долины Окса в узкое ущелье, видимо перегороженное цитаделью, развалины которой видны в городке и теперь. Кутайба не мог обойти это препятствие, пока местный землевладелец не пробился к нему и не предложил показать тропу в обход крепости — в обмен на гарантию безопасности. И в этом случае раздоры и соперничество между местными жителями дали арабам преимущество над ними. Люди Кутайбы напали на гарнизон ночью и взяли крепость. Найзак между тем бежал по маршруту, по которому проходит современная дорога от долины Окса к перевалу Саланг и Кабулу. Он укрылся в каком-то горном убежище, местонахождение которого в провинции Баглан теперь уже не установить. Кутайба преследовал его по горячим следам. Он скоро догнал мятежника и два месяца осаждал его убежище. У Найзака стали заканчиваться припасы, но свои трудности были и у Кутайбы: приближалась зима, и он опасался застрять в зимних горах.
Начались переговоры. Кутайба послал своего советника по имени Сулаим, который прихватил с собой запас еды, в том числе блюдо под названием «кабис» из фиников и очищенного масла. Изголодавшиеся мятежники набросились на еду, и Найзак понял, что если он не примет условий, то погибнет, тем более что Сулаим подчеркнул: Кутайба, если надо, готов провести здесь и зиму. Сулаим обещал сохранить ему жизнь. Найзак отнесся к его обещанию с большим подозрением: «Я чувствую, что он собирается убить меня, несмотря на обещание жизни, но его обещания оправдывают меня (в намерении сдаться) и дают некоторую надежду».
Итак, они спустились по ступеням из убежища Найзака на равнину, где паслись его ездовые животные. Сулаим всю дорогу старался подбодрить его. Когда они вышли на перевал, эскорт Сулаима выстроился позади Найзака на случай, если бы тот передумал и попытался бежать обратно в горы. Найзак увидел в этом дурной знак. Когда его доставили к Кутайбе, сбылись его самые худшие опасения. На допросе перед правителем он сказал, что Сулаим обещал сохранить ему жизнь, однако Кутайба наотрез отказался этому верить. Кутайба еще колебался, казнить его или не казнить. Вожак мятежников был опасен и легко мог стать во главе нового мятежа. С другой стороны, к гарантиям безопасности относились очень серьезно, и нарушить слово означало сильно затруднить переговоры с другими изменниками или бунтовщиками. Мнения советников Кутайбы разделились. Наконец один из них заявил, будто слышал, как правитель обещал Господу убить Найзака, если тот попадет ему в руки, а если не сделает того, то больше никогда не попросит помощи Господа. Правитель посидел, обдумывая его слова, и наконец отдал приказ: пленнику предстояло умереть. Жестокое и предательское убийство навсегда осталось пятном на репутации Кутайбы, зато остальные князья в страхе покорились ему. Смерть Найзака означала конец восстания, и большая часть князей Тохаристана. по крайней мере на время, оказались под контролем арабов.
