Там, в Испании, познакомился, сдружился, близко узнал Кузнецов многих морских и сухопутных советников, бойцов-добровольцев, которые стали со временем советскими военными руководителями, возглавили боевые действия на разных участках борьбы с фашизмом в годы Великой Отечественной войны. Среди них будущие адмиралы В. П. Дрозд, С. Д. Солоухин, С. С. Рамишвили, В. Л. Богденко, подводник С. П. Лисин, будущие генералы и маршалы Д. Г. Павлов, Н. А. Остряков, П. И. Батов, Н. Н. Воронов…
Испанский период жизни Николая Герасимовича закончился так же внезапно, как и начался. В августе 1937 года его вызвали в Москву. В Кремле Кузнецову были вручены ордена Ленина и Красного Знамени. Потом Николая Герасимовича принял Нарком обороны К. Е. Ворошилов. Маршал расспрашивал о положении в Испании, о перспективах борьбы. Кузнецов думал, что скоро опять вернется в Мадрид, в Картахену, к трудным, но уже привычным заботам. А вышло иначе. Он оказался на противоположной от Испании стороне земного шара, в далеком городе Владивостоке, о котором почти ничего не знал. Капитан I ранга Кузнецов был назначен заместителем командующего Тихоокеанским флотом.
Совсем недавно находился он в самой горячей точке планеты, в центре событий, к которым приковано было внимание всего мира, и вдруг — огромное, пустынное побережье, огромный океан, величавая природа, размеренное течение жизни, тишина… Но, как убедился вскоре Николай Герасимович, тишина и внешний покой были обманчивы. Японские милитаристы готовились осуществить свои давние замыслы, прибрать к рукам дальневосточные территории, прежде всего сказочно красивый и богатый Приморский край. В любое время могла загрохотать канонада.
Наглость, агрессивность самураев имели под собой прочную материальную основу: они полностью господствовали на море. У них было десять линкоров и столько же авианосцев, тридцать пять крейсеров, более ста эсминцев, несметное количество мелких кораблей, полторы тысячи самолетов морской авиации. А что мог противопоставить этой армаде Тихоокеанский флот, только начавший наращивать силы? Десяток эсминцев, среди них несколько устаревших, шесть сторожевых кораблей да еще торпедные катера, тральщики. Самолетов — раза в четыре меньше, чем у японцев. Лишь по подводным лодкам имелось примерное равенство.
Практически японцы могли высадить свои войска в любой точке Дальневосточного побережья, протянувшегося на тысячи километров. Советскому командованию прежде всего надо было заботиться о том, как защитить свой берег от вражеских десантов или обстрелов с моря. А ответственность за это отныне лежала на плечах Николая Герасимовича. Едва успел он ознакомиться с обстановкой, побывать в гаванях, на кораблях и береговых батареях, как поступил приказ о повышении: из заместителя Кузнецов превратился в командующего. Опять же небывалый случай: капитан I ранга (по-сухопутному — полковник) в тридцать шесть лет стал командовать целым флотом!
Столь резкий взлет не вскружил Николаю Герасимовичу голову. Успех, слава?! Некогда было даже подумать об этом — столько забот прибавила ему новая должность. На заводах строились боевые корабли, надо было торопить корабелов, добиваясь, чтобы техника отвечала самым современным требованиям. Создавалось во Владивостоке Высшее военно-морское училище, чтобы восполнить острую нехватку командных кадров. Быстро увеличивалось количество торпедных катеров и подводных лодок, способных нанести большой урон крупным кораблям противника. Очень много времени Николай Герасимович уделял усилению морской авиации и созданию береговых батарей. Авиаторы перехватят вражескую эскадру еще в море, а батареи, имеющие орудия больших калибров, укрытые в надежных казематах, перекроют все места, удобные для высадки десанта, — так считал новый командующий.
В ряде пунктов развернулось строительство аэродромов, военных городков, батарей. На своем черном ЗИС-101 (единственная такая машина была тогда в Приморье) Николай Герасимович объездил все объекты, к которым можно было добраться на колесах. Нельзя на машине — добирался на тракторе или пешком. На дальние точки — самолетом. Его энергия и настойчивость приносили свои плоды. Он, например, уверенно мог сказать, что район Владивостока наглухо закрыт для противника, авиация и мощные береговые батареи не пропустят сюда даже самые крупные вражеские корабли. А там, где высадка вражеского десанта была возможна, флот проводил учения с сухопутными войсками, готовясь совместно отражать натиск самураев. Николай Герасимович не только планировал такие учения, но и присутствовал на них вместе с Василием Константиновичем Блюхером, о котором в ту пору говорили: «Когда маршал Блюхер на Востоке, там можно иметь войск на один корпус меньше».
Василий Константинович побывал на кораблях, пригласил Кузнецова объехать полки, принимавшие участие в учениях, понаблюдать за ними на марше, в атаке. Это был первый важный урок взаимодействия разных родов войск, полученный Николаем Герасимовичем на практике, да еще под руководством такого опытного учителя, как Блюхер.