В связи со сложной обстановкой в районе Керчи 23 апреля Кузнецов направился в Краснодар. Вместе с ним вылетел назначенный главкомом Северо-Кавказского направления маршал С. М. Буденный. Наркому ВМФ было поручено проверить состояние базирования Черноморского флота в кавказских портах. Там же в Краснодаре находился и только что назначенный заместителем главнокомандующего войсками Северо-Кавказского направления адмирал И. С. Исаков.
В Новороссийске Кузнецов, выслушав доклад командира Новороссийской базы капитана 1-го ранга Г. Н. Холостякова, сразу же отправился на командный пункт ПВО. Изучив расположение зенитных батарей, он приказал срочно переместить их на новые позиции. Как вспоминает порученец наркома капитан 1-го ранга Е. А. Чернощек, начальник ПВО начал доказывать, что к рассвету он эту работу выполнить не в силах. Кузнецов ответил:
— Если к рассвету зенитные батареи не будут перемещены на указанные мою места, вы будете расстреляны.
Утром начальник ПВО доложил, что все батареи установлены на указанных наркомом местах. Когда в небе появилась большая группа немецких бомбардировщиков, их встретил огонь с новых позиций. Несколько самолетов были сбиты, остальные стали в беспорядке уходить в сторону моря. Наши истребители завершили разгром. Всего в тот день немцы потеряли шесть бомбардировщиков.
— Ермаченко, чьи это истребители? — спросил Кузнецов командующего ВВС Черноморского флота.
Тот назвал эскадрилью.
— Поедем, поблагодарим героев! — заявил Кузнецов.
Прямо на аэродроме он наградил летчиков своими именными часами и присвоил очередные воинские звания.
Между тем в штабе фронта, по воспоминаниям Кузнецова, царила неразбериха. Представитель Ставки на Крымском фронте Л. З. Мехлис вмешивался во все оперативные дела. Общего языка с ним Кузнецов не нашел. Побывав в Керченской базе и бригаде морской пехоты, он вылетел в Новороссийск, а оттуда в Поти, где тогда базировалась эскадра Черноморского флота.
Здесь Кузнецова застало известие о наступлении немцев на Керченском полуострове. Оно началось 7 мая 1942 года. Наши войска начали отход к Киммерийскому валу, но 13 мая немцы прорвали оборону и там. Несмотря на численное превосходство в районе Керчи, советские войска из-за неумелого командования потерпели тяжелое поражение. Когда положение стало катастрофическим, Мехлис попытался свалить ответственность на командира Керченской базы А. С. Фролова и потребовал у вернувшегося к тому времени в Москву Кузнецова отдать его под суд, в противном случае грозился расстрелять своим приказом.
Из воспоминаний адмирала Ю. А. Пантелеева:
«Разговор происходил по телефону „ВЧ“… Николай Герасимович резко и громко ответил: „Послушайте, Мехлис! Этого вы не посмеете сделать и права на это не имеете“. С шумом бросив трубку на рычаг телефона и весь покраснев, Н. Г. Кузнецов произнес, ни к кому конкретно не обращаясь: „Вот же прохвост какой“. А в кабинете в это время сидели на докладе заместитель наркома ВМФ Л. М. Галлер и я, как Врио начальника Главморштаба (начальник ГМШ был в госпитале). Мы переглянулись с Галлером и промолчали, чувствуя, что нарком на эту тему говорить не хочет. Должен добавить, что Сталин скоро убрал Мехлиса с фронта, но злобу на Кузнецова последний, конечно, затаил»[43].
