В Средней Азии тем временем обстановка продолжала обостряться. К югу от Ташкента начались столкновения между царскими войсками и отрядами Рустамбека, правителя Зачирчикского района.

Борьба шла не столько за «наследство» Кокандского ханства, которое сейчас по сути дела лишилось своих владений вне Ферганской долины, а главным образом за господство в Средней Азии. Крыжановский ещё во время своего визита в Ташкент в сентябре 1865 года ставил перед Черняевым задачу добиваться любыми средствами господствующего положения России в Туркестане.

После разгрома Коканда Бухарское ханство претендовало на гегемонию в этом районе и стремилось подчинить другие среднеазиатские владения. Но в военном отношении Бухарское ханство было чрезвычайно слабым и отсталым по сравнению с Россией. Это проявилось в первых же столкновениях с русскими отрядами. Плохо вооружённые и не обученные сарбазы Рустамбека отступили перед отрядом подполковника Пистолькорса, который в сентябре 1865 года занял небольшие населённые пункты Пскент и Келеучи, по дороге на Ходжент. Крыжановский предложил сохранить военный контроль над этой территорией, так как она снабжала Ташкент зерном.

Хотя между Россией и Бухарой уже развернулась вооружённая борьба, обе стороны делали попытки добиться своих целей дипломатическим путём. Эмир Музаффар направил в Санкт-Петербург посольство во главе с Неджметдином-ходжей, который уже бывал там в 1859 году. Однако царское правительство поручило вести переговоры оренбургскому генерал-губернатору. Посольство было задержано в Казалинске несмотря на протесты бухарского посланника. То же самое произошло и с русским посольством. Отправленное Черняевым в октябре 1865 в Бухару посольство в составе астронома К. В. Струве, связанного с торгово-промышленными кругами А. И. Глуховского и горного инженера А. С. Татаринова также было фактически арестовано местными властями.

Оба посольства энергично пытались выполнить возложенные на них задачи. Так, бухарский посланник, вопреки распоряжению Крыжановского, прибыл из Казалинска в Оренбург, а снаряженный им специальный полномочный гонец мулла Фахретдин добрался с письмом Неджметдина-ходжи даже до Петербурга. Это, однако, не дало результатов: письмо посланника, в котором он жаловался на нарушение дипломатических обычаев оренбургскими властями, не было принято, и мулле Фахретдину было предложено представить его Крыжановскому.

Ни к чему не привели и попытки представителей Российской империи установить нормальный дипломатический контакт с правящими кругами Бухарского ханства.

Министерство иностранных дел от имени царя уполномочило оренбургского генерал-губернатора вступить в переговоры с посланником Бухары, предъявив главное и основное требование — «поставить торговлю и политические отношения» России в Средней Азии «в самое благоприятное положение». Директор Азиатского департамента Стремоухов указывал, что дальнейшее применение репрессий против бухарских купцов необоснованно, так как русские караваны благополучно вернулись из ханства. Главное теперь — установление прямого и тесного контакта между русскими и ташкентскими купцами и использование Ташкента в качестве торговой базы России в Средней Азии.

Сам Крыжановский выработал обширный перечень условий, которые он собирался предъявить на переговорах. Он требовал учреждения в Бухаре торгового агентства России, уравнения русских купцов с бухарскими в правах, введения уменьшенного тарифа ввозных и вывозных пошлин, признания «самостоятельного» существования «Ташкентского государства» (под русским протекторатом с границами по рекам Сыр-Дарье и Нарыну) и свободного плавания русских судов по этим рекам и их притокам. В случае настойчивых претензий эмира на господство над Кокандским ханством Крыжановский считал возможным удовлетворить их.

Эти условия намечалось включить в договор, который должен был подписать эмир. Лишь после этого царские власти соглашались допустить бухарское посольство в Петербург для заключения «дружественного трактата» между Российской империей и Бухарским ханством.

Программа Крыжановского была в основном поддержана военным министром. В одобренной царем записке Милютин подчеркивал необходимость придерживаться принципа равноправия в русско-бухарских отношениях и предоставить Бухаре те же привилегии в торговле, которых добивалось царское правительство. Например, ханству разрешалось держать агентов в Оренбурге, Ташкенте или в других местах, «где того потребуют торговые интересы Бухары». Предоставляя эти льготы, царское правительство рассчитывало укрепить свое влияние в Бухаре.