Предстоящая кампания оказалась самой тяжелой, кровопролитной и, возможно, самой разрушительной в истории арабских завоеваний. Согласно сообщениям людей, якобы видевших события своими глазами, Кутайба прибыл из Ирака в Мерв, как раз когда его предшественник проводил смотр столичным войскам, прежде чем повести их за реку. Кутайба немедленно перехватил командование и обратился к воинам, призывая их к джихаду. «Господь привел вас сюда, чтобы дать силу своей религии, защитить святыни вашими руками, увеличить изобилие богатств и свершить жестовое правосудие над врагом». Он подчеркнул, что погибшие в джихаде сохранят жизнь, процитировав Коран: «И никак не считай тех, которые убиты на пути Аллаха, мертвыми. Нет, живые! Они у своего Господа получают удел». Он закончил выступление кратким лозунгом: «Исполните обетование Господа вашего, приготовьтесь пройти дальний путь и перенести великие лишения и остерегайтесь искать легких путей!» Мысль его была ясна: ни слова не было сказано о племенной или этнической солидарности — война была одна на всех мусульман, арабского или не арабского происхождения. Он использовал классическое сочетание служения Господу и приобретения богатства. Нам не дано узнать, многие ли из слышавших его воспылали ревностью к духовному и мирскому вознаграждению и многие ли слушали его с камнем на сердце, предвидя опасности и лишения.
Мы располагаем подробным описанием армии Кутайбы 715 года под конец его службы. К этому времени Кутайба, как сообщают, командовал 40 000 человек, навербованных на юге Ирана в Басре. Они принадлежали к основным племенным группам и привнесли с собой чувство племенной солидарности, хорошо служившей им на поле битвы, но в то же время и межплеменное соперничество, легко переходившее в насилие. Кроме них имелось 7000 человек из Куфы в центральном Ираке, и 7000 так называемых «мавали» — людей не арабского происхождения, обращенных в ислам и влившихся в мусульманское войско. Их возглавлял Хайан аль-Набат. Среди разных причин успехов Кутайбы была и завоеванная им верность местных войск, составлявших, если можно верить приводимым оценкам, около 12 процентов его сил. По всей видимости, они сражались с тем же упорством, что и арабы, а знание местности служило им хорошую службу, однако не все арабы готовы были принимать их как равных, и между соратниками в войске имела место скрытая напряженность. Возможно, Кутайба до того момента, когда события приняли трагический оборот, добивался успеха именно тем, что сумел объединить эти несхожие группы, внушив им единую цель — распространить владения ислама на Трансоксанию и, возможно, до самого Китая.
Кутайба немедленно открыл кампанию, направив свои войска вверх по Оксу в Тохаристан. Здесь целью его было не столько завоевание, сколько умиротворение. Он нанес официальный визит в Балх, где был радушно принят местными землевладельцами. Затем, перейдя реку, он встретился с царем Саганияна, который вынес ему навстречу дары и золотые ключи как символ покорности. В ответ ему обещана была защита от соседнего царя Шумана, к которому и направился теперь Кутайба. И здешний царь поспешил заключить мир и выплатить дань. Обезопасив свой правый фланг средствами дипломатии и демонстрацией силы, Кутайба вернулся зимовать в Мерв.
На следующий, 706 год он начал с завершения незаконченных дел на юге. Могущественнейший из местных князей, буддист Найзак, сохранял независимость своих владений в горах Бадхыз к северо-западу от Герата. Он захватил и держал в плену несколько мусульман. Кутайба послал к нему гонца с предостережением не вызывать гнева нового правителя. Найзак согласился отпустить пленников и лично отправиться в Мерв на встречу с арабским наместником. Народ Бадхыза заключил мир на условии, что Кутайба не ступит на их земли. Такие соглашения типа «живи и давай жить другим» характерны и для многих других арабских завоеваний в отдаленных районах Трансоксании.