В феврале 1972 г. БПК "Николаев" вошел в состав 70-й бригады противолодочных кораблей КЧФ и приступил к отработке курсовых задач.
Впервые БПК "Николаев" (бортовой № 539) покинул пределы Черного моря 1 марта 1973 г., направившись через Средиземное море в Бискайский залив для проведения мореходных испытаний. На бортах корабля в кормовой части появилось его название, нанесенное белой краской (на госиспытаниях оно еще отсутствовало). В тот же день в проливе Босфор корабль был впервые встречен и подробно отснят натовским катером-разведчиком, причем на выходе из проливной зоны, начиная со 2 марта, БПК был взят в сопровождение кораблями и авиацией сначала Турции, потом Греции и Италии, а также других стран НАТО, которые осуществили замеры физических полей "Николаева".
Попутно в Средиземном море провели пробную буксировку учебного легкого крейсера пр.26 "Слава" (водоизмещение до 10 000 т) со свободно вращающимися гребными винтами. При этом "Николаев" показал скорость буксировки 13,5 -13,8 уз. при 100 об/мин, что оказалось выше предусмотренных проектом значений (12,5 уз. и 125 об/мин соответственно).
На борту БПК находились Госкомиссия во главе с ее председателем П.Г.Зинчен-ко и его заместителем М.Ф.Родригесом, а также начальник штаба 5-й ОПЭСК контрадмирал ИМ. Капитанец. По плану корабль в середине апреля должен был выйти в Атлантику для проверки корпуса, механизмов и всех систем в штормовых условиях. Пройдя параллель о.Менорка в Лигурийском море, БПК в составе отряда боевых кораблей принял участие в поисковой противолодочной операции, проводившейся разнородными силами из состава 5-й ОПЭСК. Затем он произвел дозаправку топливом с танкера "Койда" ЧФ и продолжил движение на юг. Дождавшись благоприятной погоды, контр-адмирал И.М.Капитанец, убывавший в связи с новым назначением командующим Камчатской флотилией, перешел на танкер. После этого корабль взял курс на юго-запад.
28 апреля 1973 г. прошли мореходные испытания корабля в Атлантике, на волнении моря в 6 баллов. Испытания в Бискайском заливе обеспечивал БПК "Сообразительный", оснащенный соответствующей контрольно-измерительной аппаратурой. При волнении моря в 5 баллов и скорости хода 18 уз. при включенных УК достигалось уменьшение бортовой качки на нерезонансном волнении в 2,1 раза и в 2,4 при скорости хода в 24 уз. в зоне резонанса. При этом выдвижение или уборка УК обеспечивалась за три минуты вместо предусмотренных проектом четырех.
Авиация и корабли стран НАТО постоянно сопровождали корабль вплоть до завершения испытаний и возвращения в Черное море. В результате на страницах ряда зарубежных специализированных изданий появились статьи западных экспертов с достаточно высокими оценками потенциальных возможностей нового корабля. Они относили "Николаев" к классу крейсеров и отмечали его насыщенность оружием и электронными средствами.
В мае 1973 г. ВПК выполнил деловой заход в порт Аннаба (Алжир), а в период 26 сентября - 1 октября 1973 г. в составе отряда (ВПК "Скорый" и "Сметливый") под флагом командующего КЧФ адмирала В.С.Сысоева - в г.Сплит (СФРЮ). После этого "Николаев" (бортовой № 521) в составе 5-й ОПЭСК нес боевую службу, а с началом очередной арабо-израильской войны оказывал помощь вооруженным силам Египта. В ноябре корабль возвратился в Севастополь.
С июля 1973 г. командование кораблем принял капитан 3 ранга К.М.Бурковский.
В конце декабря того же года "Николаев" вышел на очередную боевую службу в Средиземное море и далее в Атлантику для завершения проверки мореходных качеств на океанском волнении. 6 января 1974 г. в Бискайском заливе он оказался в условиях 7-балльного шторма. Всхожесть на волну была хорошая, без зарывания. Оголения кормовой части и нарушений общей и местной прочности не отмечалось. На курсовом угле к волне 0° имело место сильное забрызгивание носовой части от РБУ-6000 до ходового мостика (с частотой в 15 раз за 3 минуты). Во время ударов о волну заливалась вся носовая часть до тамбуров вьюшек, с полной потерей видимости из ходовой рубки. Отмечалось среднее и сильное забрызгивание надстройки на 2/3 длины корабля, а также вертолетной площадки; постоянно заливался полуют. В целом же все корабельные системы действовали нормально, отказов в работе не наблюдалось и испытания были признаны успешными.
Во время очередной боевой службы в июне того же года "Николаев" посетил с деловым визитом порт Тартус (Сирия). С сентября в командование кораблем вступил капитан 3 ранга Ю.И.Ламзин.
В июле 1975 г. ВПК (бортовой № 523) вновь решал задачи боевой службы в Средиземном море. При заходе на посадку после выполнения очередного полета неожиданно потерял управление и упал в море корабельный вертолет Ка-25ПЛ. Причину катастрофы установить не удалось, поскольку все произошло ночью, к тому же вертолет затонул на глубине 2000 м, а экипаж погиб.
В ноябре - декабре, находясь на боевой службе в Средиземном море, "Николаев" (бортовой № 155) совершил заход в Дубровник (СФРЮ).
В 1975 - 1978 гг. корабль прошел на ССЗ имени 61 коммунара средний ремонт с внутренней модернизацией ЗРК "Шторм" до уровня "Шторм-М" (со сниженной нижней границей зоны поражения и с возможностью стрельбы вдогон и по маневрирующим целям). Во время ремонта были заменены выработавшие ресурс ГТД и проведено докование корабля в том же плавучем доке (новый док на заводе появился только в 1982 г., когда строительство всей серии "беркутов-Б" уже успешно завершилось).
В акватории завода "Николаев", головной корабль серии, стоял рядом с достраивавшимися серийным ВПК пр.1134Б "Петропавловск", а затем и "Ташкент". После окончания ремонта корабль имел новый бортовой номер 701, под которым он вышел на очередную боевую службу. Командование кораблем с 5 октября 1978 г. принял капитан 3 ранга В.И.Куренков.
В 1980 г. корабль нес боевую службу в Средиземное море уже с бортовым номером 741.
В марте 1981 г. при обеспечении боевой подготовки из-за нарушения мер безопасности при маневрировании "Николаев" (бортовой № 703) с большим трудом смог избежать столкновения с ПЛ Б-396 "Новосибирский комсомолец".
В период с 5 по 21 апреля того же года он в составе отряда боевых кораблей посетил с официальным визитом Гавану (Куба), а на обратном пути (в составе отряда) выполнял задачу по прикрытию специальных перевозок, осуществлявшихся между портами Кубы и Анголы. По возвращении в Севастополь корабль привлекали к участию в съемках художественного фильма "Правда лейтенанта Климова".
В 1981 г. ВПК в числе других кораблей флота принял участие в проведенном под руководством ГШ ВМФ в акватории Черного моря на базе 30-й дивизии ПЛК КЧФ показательном учении по управлению силами корабельной и приданной авиации с флагманского КП ТАКР "Киев".
В июне 1982 г. в рамках проводившихся совместных учений "Николаев" осуществил деловой заход в Варну (Болгария). С 25 августа его новым командиром стал капитан 3 ранга В.Н.Баранов. В июне - июле 1983 г. БПК вновь выполнил деловые заходы в болгарские порты Варна и Бургас. Вскоре после возвращения в Севастополь на надстройке, в районе носовой пусковой установки Б-192, смонтировали две 45-мм салютные пушки.
26 октября БПК "Николаев" (бортовой № 700) и СКР "Порывистый" в заранее назначенной точке Атлантики западнее Гибралтара встретили ТАКР "Новороссийск" (флаг командира 10-й ОПЭСКТОФ вице-адмирала Р.Л.Дымова) и БДК "Александр Николаев", после чего отряд начал переход к новому месту постоянного базирования на Тихий океан.
На переходе в период с 12 по 20 ноября 1983 г. корабли осуществили деловой заход в Луанду (Ангола), с 1 по 9 декабря - в Мапуту (Мозамбик), с 5 по 10 февраля 1984 г. - в Мадрас (Индия). За время визита на борту "Николаева" побывало 15 официальных лиц разного уровня.
27 февраля по завершении перехода БПК был включен в состав 175-й бригады ракетных кораблей 10-й ОПЭСК ТОФ. 13 июня командование кораблем принял капитан 2 ранга В.Е.Ионов.
1 - 3 октября совместно с ТАКР "Новороссийск", БПК "Василий Чапаев", СКР "Сторожевой", ПЛАТ К-242 и К-535, ПЛ Б-855, Б229 и Б-404, корабельными вертолетами Ка-27пл и базовой авиацией ПЛО (самолетами Ту-142) "Николаев" участвовал в поисковой противолодочной операции в Охотском море.
25 марта -17 апреля 1985 г. БПК "Николаев" (бортовой № 535) в составе КУГ 175-й бригады ракетных кораблей (ТАКР
"Новороссийск", ВПК "Ташкент", "Таллин"), КПУГ 201-й бригады противолодочных кораблей (ВПК "Василий Чапаев", СКР "Порывистый", "Ревностный") и судов обеспечения (танкеры "Владимир Ко-лечицкий", "Илим", транспорт "Абакан") участвовал в оперативно-тактическом учении флота в Японском, Филиппинском, Охотском морях и северо-западной части Тихого океана, в зачетно-тактических учениях Камчатской и Сахалинской флотилий разнородных сил, зачетном тактическом учении "Встречный бой с КУГ противника" под руководством главкома ВМФ адмирала флота Советского Союза С.Г.Горшкова.
30 марта 1985 г. БПК в составе КУГ успешно выполнил условный совместный ракетный удар по условному противнику (универсальный десантный корабль" "Тарава" ВМС США).
12 апреля 1985 г. при проведении ночных полетов в сложных метеоусловиях вертолет корабельного базирования Ка-25ПЛ при посадке на "Николаев" проскочил ВПП и сел на воду, помяв при ударе нижнюю часть фюзеляжа. Однако пилот сумел аварийно взлететь и при повторном заходе успешно выполнить посадку.
11 июля 1986 г. командиром корабля назначается капитан 3 ранга Н.А.Назаров (но фактически, пока шла передача дел, на борту оставался и предыдущий командир, капитан 2 ранга В.Е.Ионов). Однако через несколько дней произошло событие, предопределившее дальнейшую судьбу БПК.
16 июля в ходе командно-штабных учений 10-й ОПЭСК в Японском море, на подходе к проливу Лаперуза, в ночное время и при благоприятных метеоусловиях БПК "Николаев" столкнулся с БПК "Строгий". Как стало известно по результатам работы комиссии, события развивались следующим образом. Корабли 183-й бригады противолодочных кораблей 10-й ОПЭСК ТОФ в составе БПК "Таллин", "Николаев". "Строгий" и "Адмирал Спиридонов" в составе КПУГ осуществляли отработку совместного плавания. Они следовали строем кильватера (уравнитель - БПК "Таллин") курсом 95е со скоростью хода 9 уз., дистанция в строю между кораблями - 20 кбт. Справа от кильватерного строя, почти на траверзе замыкавшего строй "Адмирала Спиридонова" шел параллельным курсом на дистанции 9 кбт японский фрегат DE-213 "Китаками", догонявший советские корабли на скорости 21 уз., осуществляя слежение.
В 3.12 ночи с БПК "Таллин" на корабли КПУГ по УКВ-связи прошла команда на изменение курса на обратный до 275° поворотом вправо (то есть в сторону японского корабля) способом "все вдруг" и увеличение скорости хода до 18 узлов(!). Контроль ближней надводной обстановки на кораблях КПУГ осуществлялся неудовлетворительно, причем в нарушение всех требований МППСС-72 находившийся поблизости иностранный корабль об изменении курса кораблями по радиосвязи предупрежден не был. Так, на концевом "Спиридонове" сигнал вообще разобрали неправильно, полагая, что поворот будет осуществляться последовательно, и продолжали движение прежним курсом. А на "Строгом" обнаружили присутствие японца только в 3.14 в ходе поворота на новый курс. Обнаружив, что пеленг на японский фрегат не меняется, а дистанция быстро сокращается, командир "Строгого" в 3.15 начал подворачивать влево, пытаясь таким образом избежать столкновения с японцем, оказавшимся у него на траверзе. Однако тем самым он фактически стал быстро сближаться с БПК "Николаев", уже начавшем поворот вправо (на последнем на командирской вахте в управлении кораблем находился не допущенный к самостоятельному управлению кораблем помощник командира, а командир в это время спал в кресле на ходовом мостике).
На "Николаеве" заметили опасность и, уклоняясь, в 3.16 начали поворот влево, выходя на курс завершавшего циркуляцию флагманского "Таллина". Последний также завершал циркуляцию, и в случае отворота "Николаева" влево оказывался у него на курсе. В 3.16, заметив начало поворота советских кораблей, резко отвернул вправо, уходя в сторону, и японский фрегат. Оказавшись в сложной ситуации, стремясь избежать столкновения с флагманским кораблем, "Николаев" в 3.18 застопорил машины. Но следовавший за ним БПК "Строгий", несмотря на перекладку руля "право на борт" и беспорядочные попытки то застопорить ход, то работой машин уклониться от столкновения, не успевал погасить инерцию и на курсовом угле в 40° со стороны кормы нагнал "Николаев" - в 3.19 последовал первый удар форштевнем в правый борт. Отброшенный силой инерции, "Строгий" вновь и вновь наносил рубящие удары в надводную часть "Николаева" - в общей сложности, их насчитали семь. Были повреждены на большом протяжении надводный борт в районе надстройки (коридор трасс), ПУ ПЛУР "Метель", а также артиллерийские установки правого борта. Короткого замыкания и пожара удалось избежать благодаря своевременному обесточиванию потребителей. "Строгий" лишился форштевня. Человеческих жертв не было, но корабли, хоть и дошли до базы своим ходом, на длительное время оказались выведенными из строя. Для восстановления их боеготовности требовался заводской ремонт и большие материальные затраты.
По заключению комиссии, расследовавшей это ЧП, причинами тяжелого происшествия стали "безответственность, халатность и недисциплинированность как командования 183-й бригады противолодочных кораблей, так и командиров обоих БПК". Целый ряд офицеров был наказан, в частности, сняты и назначены с понижением командиры "Николаева" (капитан 2 ранга В. Е. Ионов) и "Строгого" (капитан 3 ранга В.А.Фадеев), а также командир и начальник штаба 183-й бригады. После проведения силами "Дальзавода" ремонта, призванного обеспечить возможность межтеатрового перехода корабля, в мае - июле 1987 г. БПК "Николаев" совершил переход в Севастополь, а с 11 ноября 1987 г. был поставлен на завод имени 61 коммунара в Николаеве для проведения ремонта и модернизации.
