Устроители Туркестана. Туркестанские генерал-губернаторы - стр. 26
Начальник Среднеазиатского департамента МИДа П. Н. Стремоухов писал туркестанскому генерал-губернатору: «Из вашего письма я вижу, что вы смотрите на Красноводск, как на средство, облегчающее военную экспедицию в Хиву. Наше министерство и вообще правительство смотрит на него иначе, а именно, как на новые ворота для нашей торговли, и, в крайнем случае, как на благотворную угрозу или внушение Хиве. Нам было бы желательно, чтобы посредством этого пункта широко развилась торговля, которая своею выгодностью докажет Хиве пользу добрых к нам отношений, а в то же время глупый хан поймет, что и до него добраться теперь уже сравнительно легко».
Проект, тем не менее, был одобрен и в ноябре 1869 года небольшой военный отряд под командованием полковника Н. Г. Столетова высадился на пустынном побережье Муравьёвской бухты Красноводского залива. Здесь, на месте древнего колодца Шагадам, и было основано укрепление Красноводск.
Вся операция была строго засекречена, поскольку задача состояла в постройке постоянной крепости, и ни англичане, ни персы, ни хивинцы не должны были раньше времени об этом узнать.
Сразу после основания Красноводска Кауфман вновь отправляет письмо в Хиву, требуя безопасности русско-хивинской торговли, допуска русских купцов в ханство, а также прекращения вмешательства в дела казахских племён. И вновь ответа не последовало. Более того Мухамед-Рахим стал активно готовиться к войне. В самой Хиве соорудили оборонительную башню с 20 пушками, чтобы не допустить прохода русских кораблей перегородили главный фарватер Аму-Дарьи и построили новые укрепления Джан-Кала и Кара-Томак.
Константин Петрович был опытным государственным деятелем и умел ждать. Поэтому последовал совету Стремоухова «вооружиться терпением и дать обстоятельствам более обрисоваться». Более того не посчитал для себя унижением вступить в переписку с диван-беги (министром иностранных дел) Хивы всё с теми же предложениями, на которые вновь последовал дерзкий ответ.
Военный историк М. А. Терентьев писал впоследствии: «Видя из тона письма, что обаяние Красноводского отряда уже ослабло и что наша настойчивость и угрозы без поддержки их вооружённою рукой ничего не стоят в глазах хивинцев, генерал Кауфман представил военному министру свои соображения относительно совместных действий против Хивы со стороны Туркестана и Кавказа, чтобы решительным ударом низвести Хиву с того пьедестала, на котором она стоит, кичась своей недоступностью и нашими прежними неудачными попытками вразумить её».
Отношения с Хивой продолжали оставаться напряженными, но политика в отношении Хивы еще не была определена окончательно ни в Петербурге, ни в Ташкенте.