Заснування села Карнаухівські Хутори належить до першої половини XIX столітті. Першими його поселенцями були вихідці з села Карнаухівки (тепер — частина міста Кам ‘янського).
Село Миколаївка було засноване у 18 столітті запорізькими козаками. Інтенсивне заселення села пов’язане з переселенням сюди вихідців з села (нині місто) Кам’янського наприкінці 19 ст.
Станом на 1886 рік на Карнаухівських хуторах Діївської волості Катеринославського повіту Катеринославської губернії мешкало 633 особи, налічувалось 111 дворових господарств, існувала православна церква.
За переписом 1897 року кількість мешканців зросла до 1246 осіб (573 чоловічої статі та 673 — жіночої), з яких 1235 — православної віри.
Станом на 1923 рік у селі Миколаївка мешкало 1495 осіб.
У 1929 році створюються колгоспи: у Миколаївці — «Дзержинець», у Василівці — «Червона Армія», у Карнаухівських Хуторах — «Ворошилівський» та «Переможець».
