Команда создана в 1920 году. В разные годы выступала под названиями «Металлист», команда завода имени А. Марти, «Судостроитель», «Авангард», «ЭВИС», СК «Николаев», МФК «Николаев».

В чемпионате бывшего Союза команда судостроительного завода, носившего уже имя Носенко, впервые участвовала в группе «В» в 1937 году, а годом раньше дебютировала в кубке СССР.

После окончания Второй мировой войны «Авангард» возобновил выступления в чемпионате СССР. В 1954 году заводские футболисты впервые выехали зарубежную поездку в Чехословакию, где провели три товарищеские игры: «Банник» (Гвидлов) – 3:0, Спартак» (Поважска Быстрица) – 2:1 и «Слован» (Нитра) – 2:2.

В 1957 году городу Николаеву вновь было предоставлено место в классе «Б» чемпионата СССР. С 1966 года «Судостроитель» выступал во II подгруппе класса «А». В 1969 году дошел до полуфинала розыгрыша Кубка СССР.

Лучшие результаты, достигнутые в чемпионатах бывшего Союза: 1 место – 1960 (класс «Б», 1 зона), 1968 год (класс «А», II группа, 2 подгруппа), 1974 (вторая лига, 6 зона); 2 место – 1971 (вторая лига, 1 зона), 1990 (вторая лига, 1 зона); 3 место – 1958 (класс «Б», 1 зона), 1959 (класс «Б», 1 зона), 1973 (вторая лига, 1 зона), 1984 (вторая лига, 6 зона), 1985 (вторая лига, 6 зона).

В сезоне 2005/2006 годов МФК «Николаев» занял первое место в группе «Б» второй лиги и завоевал путевку в первую лигу. В своем дебютном сезоне 2006/07 гг. в первом дивизионе николаевский клуб с 46 набранными очками занял 13 место.