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