Līdz 19. gadsimta sākuma zināma kā kazaku ziemošanas apmetne Kuca Balka (Куца Балка). 19. gadsimta sākumā izveidojās pastāvīgs ciems Semiņivka (Семенівка), kurā apmetās ieceļotāji no Poltavas, Čerņihivas, Kurskas apkārtnes, kā arī no Besarābijas. 1810. gadā netālu no ciema apmetās turīgs ieceļotājs no Hersonas guberņas Pavlo Triska kopā ar 119 citiem ieceļotājiem. Ciemi apvienojās un tie ieguva Novopavļivkas (Новопавлівка) vārdu. 1820. gados Novopavļivka kļuva par pagasta centru. Pēc militāro apmetņu sistēmas izveidošanas Novopavļivka tika pakļauta Bugas ulānu divīzijai un ieguva tagadējo vārdu ‘Jaunā Buga’. 1860. gadā Novijbuha ieguva miesta statusu, bet 1961. gadā kļuva par pilsētu.