Землі Куцівки (Новгородки) входили до складу Запорозької Січі. Після ліквідації Запорозької Січі Куцівка стала державним поселенням.
Історична хронологія селища починається з 1768 року. Тоді цей населений пункт був запорозькою слободою Куцівкою, заснований запорізьким полковником Бугогардівської паланки Афанасієм (Панасом) Івановичем Куцим. Перші мешканці — запорозькі козаки Дядьківського куреня, згодом також переселялися вихідці з Полтавської губернії.
З 1821 року Куцівка — військове поселення, центр округу. У 1822 року Куцівка перейменована на село Новгородку на честь Новгородського полку, що тут квартирував.
Після ліквідації військових поселень Новгородка — державне село, яке в 1860 року отримало статус містечка і стало центром волості. Східну околицю Новгородки, де розташовувався Новгородський полк, жителі селища і тепер називають «штабом», а заглибину річки Кам’янки, де стояла лазня для військових — «банею».
На початок XIX століття Новгородка була вже великим поселенням, що розміщувалося на берегах річки Кам’янки та на схилах балок Тернової та Котенкової.
Станом на 1886 рік у містечку, центрі Новгородківської волості Олександрійського повіту Херсонської губернії, мешкало 4928 осіб.
У 1917 році село входить до складу Української Народної Республіки.
Внаслідок поразки визвольних змагань на початку лютого 1918 року в містечку встановлено радянську владу. Почалася чорна смуга в історії села і її жителів — репресії 1918—1921, голод 1921—1922, знищення церкви і земської освіти, розкуркулення і колективізація 1929—1931, Голодомор 1932—1933, репресії 1937—1938, Друга світова війна 1941—1944, репресії 1944—1952, голод 1946—1947 років. Після такого геноциду українського народу, населення Новгородки зменшилось в рази.
