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