Засноване 1861 року як Новоселівка нащадками запорожців, вихідцями з Бессарабії та кріпаками-утікачами. У селі діяла Свято-Миколаївська церква з 1872 року, при ній була відкрита парафіяльна школа. 1883 року було збудоване, за кошти громади, перше в селі приміщення школи з однією класною кімнатою та квартирою вчителя, де навчалося 12 учнів.
З 1923 року Новомиколаївка – центр сільської ради.
Під час Другої світової війни на фронтах воювало 500 новомиколаївців. 200 з них були нагороджені орденами та медалями СРСР. На честь 254 воїнів-односельчан, які положили своє життя, встановлено обеліск. В роки тимчасової окупації села німцями діяло підпільне патріотичне об’єднання, яким керував А. С. Коваленко.
