Основано как село Грязное. Согласно Историко-географическему словарю Саратовской губернии село Грязное состояло из двух частей — деревни Грязной (также Грязной Курган, Еремин Курган) и деревни Тополевки. Тополевка была заселена в 1826 году, Грязная в 1829 году русскими государственными крестьянами. При поселении крестьяне получили от казны надел в 10250 десятин удобной и неудобной земли.
В 1886 году построена церковь святого Николая Чудотворца. В 1894 году в селе имелись 2 мелочные и 1 винная лавки, 5 ветряных мельниц и 3 маслобойни. Крестьяне занимались преимущественно хлебопашеством[3].
С 1928 года — административный центр Грязновского сельсовета Ольховского района Камышинского округа (округ ликвидирован в 1934 году) Нижневолжского края. С 1935 года — в составе Балыклейского района Сталинградского края[4] (с 1936 года — Сталинградской области, с 1961 года — Волгоградской области). В 1959 году Грязновский сельсовет был упразднён, территория передана в состав Ягодновского сельсовета. В 1963 году Балыклейский район был расформирован, Ягодновский сельсовет передан Камышинскому району[5]. Указом Президиума ВС РСФСР от 15 августа 1963 года № 33(255) село Грязное было переименовано в село Новороссийское[6]. В составе Ольховского района — с 1966 года[7].
По автомобильным дорогам расстояние до областного центра города Волгоград — 160 км, до районного центра села Ольховка — 24 км. Село Ягодное расположено в 10,5 км к северо-востоку[10].
