Ворошилов информировал Ставку о положении дел в Приморской армии. С конца февраля началась подготовка операции по освобождению Крыма. Замысел Ставки заключался в том, чтобы нанести главный удар с севера, от Перекопа и Сиваша; это должны были сделать войска 4-го Украинского фронта (командующий — генерал армии Ф. И. Толбухин). Вспомогательный удар из района Керчи предстояло осуществить Приморской армии.
Провести операцию поначалу намеревались в марте 1944 года, но неблагоприятная погода в Крыму, сильные штормы в Азовском море не позволили сделать это. А. М. Василевский, координировавший действия 3-го и 4-го Украинских фронтов, побывал на Сиваше в 51-й армии генерал-лейтенанта Я. Г. Крейзера, ознакомился с подготовкой к наступлению и сообщал 3 марта в Ставку: «Прошедший вчера и сегодня дождь окончательно вывел из рабочего состояния дороги. Весь автотранспорт стоит на дорогах в грязи. С трудом кое-как работают лишь тракторами. От попытки пробраться к Крейзеру на машинах пришлось отказаться, летели на У-2. При таком состоянии дорог начинать операцию нельзя, не сумеем за продвигающимися войсками подать не только пушки и снаряды, но даже продовольствие и кухни…» Влияло на изменение сроков и положение на соседних участках фронта. Поэтому Ставка разрешила начать освобождение Крыма после того, как наши войска выйдут к Одессе.
К концу марта подготовка завершалась. Утром 29 марта в Кривом Роге состоялась встреча маршалов Ворошилова и Василевского. Они обсудили ход подготовки, согласовали вопросы взаимодействия 4-го Украинского фронта и Приморской армии. Настроение у маршала было хорошим. На советско-германском фронте наши войска наступали, за несколько дней до этого — 26 марта 1944 года — они достигли государственной границы на реке Прут. Было очевидно, что освобождение всей оккупированной гитлеровцами территории нашей страны уже не за горами. Впоследствии Василевский писал: «Память об этой очередной встрече храню до сих пор. Радушие и гостеприимство всегда были свойственны Клименту Ефремовичу…»
На следующий день, уже в Мелитополе, совещание продолжалось. Итогом его был следующий доклад Верховному: «1. Считаем необходимым принятие решительных мер по организации настоящей блокады Крыма, которая воспрепятствовала бы переброске войск и материальных ресурсов как в Крым, так и обратно… 2. 4-й Украинский фронт полностью подготовлен к выполнению задачи. Выпал глубокий снег, который вывел аэродромы из строя, а частые метели и туманы исключают возможность проведения нормальной работы артиллерии. Если погода позволит, то 4-й Украинский фронт начнет операцию не позже 5 апреля 1944 года. На Керченском направлении предлагаем начать через 2–3 дня после начала Перекопской операции. Просим утверждения.
1 апреля Ворошилов был уже в штабе Приморской армии. Вместе с Еременко они детально рассмотрели план Керченской операции.
На севере войска 4-го Украинского фронта начали операцию 8 апреля. Гитлеровцы упорно сопротивлялись, но оборона их был прорвана, и 11 апреля наши части вступили в Джанкой. Приморская армия начала боевые действия в 22 часа 10 апреля, и к утру ее части освободили Керчь. Противник поспешно отходил на запад. 13 апреля враг был выбит из Евпатории, Симферополя и Феодосии, 14 апреля — из Бахчисарая и Судака, 15 апреля подвижные части 4-го Украинского фронта достигли внешнего оборонительного обвода Севастополя. В то же время войска Приморской армии освобождали одну за другой здравницы Южного берега Крыма. В ночь на 16 апреля они очистили от врага Ялту и подошли с востока к Севастополю…
Прекрасен весенний Крым! В эти дни на его солнечных дорогах Ворошилов вспоминал ноябрь 1920 года, когда он с бойцами 1-й Конной так же рвался к Севастополю, к морю, чтобы сбросить в него врага. Красоты Крыма, этого райского уголка нашей страны, неудержимо влекли гитлеровцев: они считали, что здесь до XVI века проживали предки «нации господ» — готы. Гитлер собирался выселить из Крыма советских людей и создать здесь немецкие колонии, Гиммлер уже приступил было к их организации… Теперь же, спешно покидая крымскую землю, захватчики уничтожали все, что успевали…
15 апреля Ворошилов, сопровождаемый заместителем командующего Отдельной Приморской армией генерал-лейтенантом К. С. Мельником, встретился в Сарабузе Болгарском с Василевским. Обсуждая проблемы взаимодействия войск во время предстоящего штурма Севастополя, маршалы пришли к мнению о целесообразности подчинения Приморской армии командованию 4-го Украинского фронта. Такого же мнения придерживался и Верховный Главнокомандующий. В ночь на 16 апреля был получен соответствующий приказ Ставки.