Правда, колонизация кочевников проходила не совсем гладко. В 1735 году из-за непомерных притеснений со стороны уфимского губернатора башкиры подняли восстание, которое продолжалось шесть лет. На его подавление были посланы войска под командованием генерала А. И. Румянцева – отца знаменитого фельдмаршала. Огнем и мечом они прошлись по мятежным землям. К июню следующего года большая часть Башкирии была разорена, но ее племена продолжали сопротивление. И лишь после того, как на помощь Румянцеву со стороны Сибири были двинуты войска генерала Татищева, мятежники были разгромлены. Непокорность России стоила башкирам 30 тысяч человеческих жизней. За боевые заслуги Румянцев был награжден чином генерал-аншефа, а Татищев получил орден Святого Александра Невского.
Примерно в это же время началась жестокая война между киргизскими племенами, разделившимися на Большую, Среднюю и Малую орды. В ходе этой борьбы Малая орда, оттесненная к Уралу, в 1730 году признала над собой власть России. В период с 1735 по 1742 год были произведены укрепления Оренбургское, Табинское, Губерлинское, Озерное и три форпоста, составившие основу будущей оренбургско-уральской линии. В последующие годы эта линия была продолжена до китайской границы, вдоль которой было выстроено 141 укрепление на расстоянии одного дневного перехода друг от друга. На этой линии четко обозначились два плацдарма для будущего наступления на Среднюю Азию – оренбургский и сибирский, где постоянно накапливались силы, необходимые для дальнейших действий.
Во время своего короткого правления Павел I успел отдать совершенно непродуманный приказ Донскому и Уральскому казачьим войскам готовить поход на Индию через Среднюю Азию. К счастью, эта экспедиция, заранее обреченная на неудачу, не состоялась из-за гибели императора, а Александр I, едва лишь вступив на престол, отменил указания отца.
Между тем немедленное наступление России на Среднюю Азию продолжалось. В течение 20—30-х гг. XIX века русские пограничные посты постепенно продвинулись на 600–700 верст южнее старой Сибирской линии и достигли Голодной степи. Обитавшие там киргизские орды начали добровольно переходить в русское подданство.
Сложнее данный процесс происходил на Оренбургской линии, где кочевники под влиянием Хивы всячески сопротивлялись русскому присутствию. С этим было решено покончить императором Николаем I. Начался следующий этап завоевания Средней Азии, связанный с деятельностью военного губернатора Оренбурга генерал-адъютанта В. А. Перовского, который в отличие от Бековича не ставил перед собой глобальных, заранее не выполнимых задач. В изданном им в середине ноября 1839 году приказе целью экспедиции ставилось: «Силой оружия обеспечить на будущие времена права и пользы российских подданных, положить конец грабежам и насилиям, избавить томящихся в Хиве невольников, внушить должное уважение к имени российскому и упрочить то влияние, которое неоспоримо принадлежит России и которое одно может служить залогом сохранения мира в сей части Азии».
Для проведения экспедиции в Оренбурге были собраны значительные силы, включавшие 15 рот пехоты и 3 казачьих полка. В составе этих войск имелось 5333 человека и 16 артиллерийских орудий. Кроме того, для транспортировки военных грузов среди местного населения было мобилизовано 2400 киргизов-погонщиков и более 12 тысяч верблюдов.
В конце ноября войска Перовского несколькими колоннами начали выдвижение на юг из Оренбурга. Путь оказался нелегким. Морозы, снежные бури, а также мелкие частые стычки с хивинцами постоянно снижали темпы дневных переходов. Достигнув Эмбионского укрепления, русские войска были вынуждены сделать остановку более чем на месяц, чтобы подтянуть тылы и собраться с силами. Продолжилось движение колонн в январе 1840 года. И сразу же возникли новые трудности: начался массовый падеж верблюдов. К концу месяца их поголовье сократилось в два с половиной раза.
Из-за недостатка продовольствия и фуража Перовский 1 февраля принял решение вернуть войска в Эмбионское укрепление. Двухнедельный обратный путь также оказался нелегким. Он был усеян трупами павших животных и обломками брошенного военного имущества.
В Эмбионском укреплении экспедиционные войска находились до середины мая. Затем, совершив еще один трудный переход, они в начале июня вернулись в Оренбург. За время похода, даже не вступив в огневое соприкосновение с противником, отряд от болезней потерял более 1200 человек.