Заселення Північного Причорномор’я, де і знаходиться Веселинове, почалося в період пізнього палеоліту, тобто приблизно 15-16 тис. років тому. Однак стоянок прадавніх людей на території Веселинівщіни того періоду не виявлено, хоча в 50 км від Веселинова — у селі Олександрівка Вознесенського району – знайдені сліди мезолітичних мисливців.
Не переривалося життя на цій території і в епоху міді та бронзи.
У IX-VIII століттях до н. е. на території сучасної Миколаївщини жили кімерійці, а згодом їх витіснили племена скіфів, сліди яких збереглися на околицях Веселинова – тут знайдено близько 20 курганів епохи бронзи, скіфського та сарматського періоду.
Поселень слов’янських племен на території Веселинова не знайдено, так само як і поселень Київської Русі і Великого князівства Литовського.
З XV по XVIII століття територія Веселинова входила до складу Туреччини.
За Ясським мирним договором 1791 року до Росії відійшла так звана Очаківська земля (правий берег річки Південний Буг). З цього часу і починається державна колонізація краю і в тому числі Веселинівщини. В історії Північного Причорномор’я важливе місце займає ясновельможний князь Григорій Олександрович Потьомкін-Таврійський. Під його керівництвом відбувалося завоювання Північного Причорномор’я, штурм Очакова, приєднання Криму, освоєння (заселення) диких степів.
В кінці XVIII століття, за велінням імператриці Катерини II, Потьомкіним було організовано переселення в ці пустельні місця жителів Центральної Європи, в основному, з німецьких князівств. Російська держава взяла на себе всі витрати з переселення, включаючи харчування переселенців в дорозі. Німецьких колоністів на 10 років звільняли від податків, земельної повинності, рекрутських наборів і військових постоїв. Їм гарантувалася свобода віросповідання. Кожна сім’я отримувала по 60 десятин землі у вічне і спадкове користування. Так в західній частині Миколаївщини з 1809 по 1832 роки виникли німецькі колонії Раштад (Поріччя), Рорбах (Новосвітлівка), Ландау (Широкий лан), Ватерло (Ставки) та інші. Але все ж більшість переселенців (приблизно 120 тис. Селян) було з Північного Уралу та Центральної Росії. Тоді ж землі по берегах річки Чічіклеі Катерина II подарувала полковнику Веселинове – в числі інших російських дворян, яким роздали 4,5 млн десятин завойованих земель. На ці землі поміщики переселяли своїх кріпаків. На землях полковника Веселинова з’явилося однойменне село – Веселинове. У 2-й половині XIX століття його перейменували в Олександрівку – по імені дочки поміщика, але в кінці XIX століття йому повернули стару назву. З моменту заснування на початку 1790-х рр., село Веселинове входило в Ольвіопольський повіт спочатку Катеринославської, з 1797 по жовтень 1802 рр. – Новоросійської, з жовтня 1802 по травень 1803 – Миколаївської, а з травня 1803 р.- Херсонської губернії.
Указом від 19 жовтня 1825 був утворений Одеський повіт за рахунок частини Херсонського і Тираспольського повітів, але ця реорганізація Веселинове не торкнулася – він залишився в Ольвіопольському повіті. У 1828 році Ольвіопольський повіт був скасований, і частина його території разом з Веселинове відійшла до Тираспольському повіту.
У 1834 році від Тираспольського повіту була відділена частина території, на якій був утворений новий повіт – Ананьївський. До нього увійшло і село Олександрівка (Веселинове) Покровської волості. І перебувало воно в такому підпорядкуванні аж до територіально-адміністративних реформ початку XX століття.
Розвивалося село дуже повільно, про що свідчить статистика чисельності населення протягом ряду років:
1859 рік – 30 кріпаків
1874 рік – 56 селян
1887 рік – 66 селян
1896 – 117 чол.
1914 рік – 800 чол.
1924 рік – 1001 чол.
До 1918 року Веселинове було одним з сіл, яких було досить багато в Північному Причорномор’ї, і тільки в січні 1918 року воно стало волосним центром Ананьївського повіту Херсонської губернії, а в лютому 1920 року – волосним центром Ананьївського повіту Одеської губернії. Мабуть, це стало можливим тому, що через Веселинове проходив як поштовий тракт Одеса – Київ, так і залізниця Одеса – Бахмач. Ця дорога з’єднувала волость з центральними містами набагато швидше, ніж попередній волосний центр – Покровка (хоча в Покровці було 484 двори з 2773 жителями).
У 1939 році Веселинове стало районним центром Одеської області. Під час Великої Вітчизняної війни в 1941—1943 роках. селище знаходилося під німецькою окупацією. У Миколаївську область Веселинове увійшло в якості районного центру в травні 1944 року.
У 1963 році Веселинівський район був розформований, проте в 1965 році Веселинове знову стало районним центром Миколаївської області, яким воно залишалося аж до 2020 року, коли цей район було скасовано, а селище міського типу увійшло до складу укрупненого Вознесенського району, ставши центром однойменної громади.
У 1969 році чисельність населення становила 5,4 тис. осіб.
Станом на початок 1971 року тут діяли прядив’яний завод і інкубаторно-птахівнича станція.
У січні 1989 року чисельність населення становила 8123 чоловік .
Станом на 1 січня 2013 року чисельність населення становила 6104 людини.
