Василий Мжаванадзе и на республиканском съезде, и на XXIII съезде КПСС критиковал воспоминания академика и бывшего посла в Англии Ивана Михайловича Майского, опубликованные в «Новом мире» — за «слишком вольное обращение с историей». Василию Павловичу не понравилась критика Сталина.

В мартовские дни 1956 года молодой Шеварднадзе занял благоразумную позицию. Сам он в манифестациях не участвовал, но и не спешил клеймить ее участников. Это оценили, и из Кутаиси его перевели в столицу секретарем ЦК республиканского комсомола. Ему было двадцать восемь лет. На следующий год он возглавил грузинский комсомол.

Он понравился Василию Мжаванадзе, которому события 1956 года никак не повредили. А на следующий год Мжаванадзе решительно поддержал Хрущева, когда Молотов, Маленков, Каганович и Булганин попытались снять его с поста Первого секретаря. В благодарность Никита Сергеевич сделал Мжаванадзе кандидатом в члены президиума ЦК. Это укрепило его позиции, обезопасило и от московских контролеров.

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

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

Благожелательное отношение первого секретаря помогло Эдуарду Шеварднадзе пройти по всем ступенькам комсомольской карьеры. А вот партийная карьера началась у него не слишком удачно. В 1961 году Мжаванадзе сделал его первым секретарем Мцхетского райкома, но Эдуард Амвросиевич жаловался друзьям, что его обидели: район дали красивый, исторический, но малозаметный в экономической и политической жизни республики. Через два года его все же перевели первым секретарем одного из райкомов в столичный Тбилиси. Его знакомые по комсомолу помнят, что уже в те годы Шеварднадзе с горечью рассказывал о масштабах коррупции в республике. Называл Василия Павловича Мжаванадзе мягким и доверчивым человеком, великодушно считая, что во всех безобразиях в республике были виноваты плохо подобранные кадры. Но на этот счет есть и другие мнения.

Когда Шеварднадзе попытался обратить внимание хозяина республики на недостойные поступки некоторых людей из его окружения, Эдуарда Амвросиевича убрали с партийной работы и сделали сначала первым заместителем, а через год республиканским министром охраны общественного порядка (после переименования ведомства в 1968 году он стал министром внутренних дел). Назначение расценили как желание Мжаванадзе убрать молодого человека с партийной работы. Переход в МВД мог поставить крест на многообещающей карьере. Но опасный для начинающего политика пост ему не повредил. Напротив, в Москве приметили молодого и искреннего борца с коррупцией. Рассказывали, как он приказал не выпускать утром такси из таксопарков, а по Тбилиси все равно ездили машины с «шашечками», и всех частников, выдававших себя за таксистов, переловила милиция.

Он пытался бороться с коррупцией всеми доступными ему методами. Проводил чистки следственного и тюремного аппарата, набирал в МВД молодежь из комсомола. Но со временем убедился, что ничего не помогает. Система перевоспитывала людей в своем духе. Семь лет он служил министром внутренних дел, получил звание генерал-майора. Ему часто потом припоминали, что он сажал людей в тюрьмы. Зато никто не мог сказать, что он брал взятки или вообще замешан в чем-то недостойном. А про его предшественника нечто подобное говорили открыто.

В МВД охотно переводили с партийной работы, но обратной дороги не было. Максимум, на что он мог рассчитывать, это на перевод в союзное министерство, в Москву. Тем более, что министр внутренних дел СССР Николай Анисимович Щелоков благоволил своему грузинскому коллеге. Но обстоятельства сложились для Шеварднадзе очень удачно.

В начале семидесятых Брежнев стал менять партийное руководство в центре и на местах. Там, где у него были свои люди, вопрос решался легко. На Украине вместо хрущевского человека Петра Ефимовича Шелеста первым секретарем в 1972 году стал старый друг Брежнева Владимир Васильевич Щербицкий. В том же году настала очередь Мжаванадзе. Желание сменить первого секретаря в Грузии созревало у Брежнева постепенно.

Тот же Петр Шелест обратил внимание на один показательный эпизод. В конце ноября 1970 года в Ереване отметить пятидесятилетие образования Советской Армении собрались все первые секретари национальных республик. Приехал и Брежнев. Вечером собрались вместе поужинать. Первый секретарь ЦК Компартии Азербайджана Гейдар Алиевич Алиев, произнося тост, сказал:

— Закавказские республики живут дружно, поддерживают друг друга. Наш аксакал Василий Павлович Мжаванадзе нас направляет, мы с ним советуемся по всем вопросам.

Шелест пишет, что слова об «аксакале» восприняли как шутку все, кроме Брежнева, который насторожился и завел разговор об опасности групповщины и национальной обособленности. Петр Ефимович считает, что Брежнев поставил в личном деле Мжаванадзе жирный минус.

Но дело скорее было в другом. Брежнев еще не болел, был бодр, хотел что-то сделать, а Мжаванадзе шел уже к семидесятилетию. Нужен был новый человек. Говорят, что именно Щелоков обратил внимание генерального секретаря на подающего надежды республиканского министра внутренних дел. Сам Шеварднадзе считает, что его имя Брежневу назвал тот же Гейдар Алиев, первый секретарь ЦК Компартии Азербайджана, а до того председатель республиканского КГБ.

К Алиеву в те годы в Москве относились с особым уважением. Став первым секретарем, Алиев провел массовую чистку кадров, снял с работы около двух тысяч чиновников. Часть из них была арестована, в доход государству поступило немалое число конфискованных ценностей. Правда, со временем станет ясно, что масштабы коррупции в республике не уменьшились. При Алиеве, по существу, просто произошла смена республиканской элиты. А новое руководство желало так же наслаждаться жизнью, как и прежнее. Виктор Михайлович Мироненко, в те годы видный работник Комитета народного контроля СССР, рассказывал, как, приехав в Азербайджан с проверкой, был поражен:

— В магазинах, в государственной торговле, все было как на рынке — продавцы самостоятельно устанавливали цены, покупатели с ними торговались. Продавец вел себя так, словно магазин принадлежал ему, а не государству…

От Шеварднадзе ждали таких же подвигов, как и от Алиева. Решение сделать министра внутренних дел республики первым секретарем ЦК далось Брежневу нелегко. Но Шеварднадзе действительно с первого взгляда внушал симпатию и рождал уверенность в том, что он способен справиться с любым делом.