Новоселівка, невеличке село, що загубилося серед українських степів, до нього не потрапиш прямою дорогою, та потрібно лиш звернути на невелику, хоч і асфальтовану та фактично польову дорогу, і перед вами відкриється село, більшості будинків в ньому давно перевалило за сотню років.

Перша згадка про населений пункт на місці сучасного села, зустрічається у праці Пивовара А.В. «Поселення Херсонської губернії за повітовими алфавітами 1856 року», зокрема, у тій частині роботи, де мова йде про Одеський повіт вказаний населений пункт – хутор Голіков, що на той час мав 6 дворів та належав громадянину Голікову, для уточнення потрібно сказати, що він був всього на всього однофамільцем Івана Григоровича Голікова господаря сусіднього села Новогригорівка, і займав посаду звичайного канцеляриста в місті Миколаєві.

Наступне джерело, у якому міститься інформація про минуле Новоселівки, це «Список населених місць Херсонської губернії по свідченням 1859 року», дана книга видана у Санкт-Петербурзі у 1868 р. Щодо села у ній сказано таке: хутір Булгарка (Голіков) розташований при колодцях на балці Кам’яній, кількість дворів 10, кількість жителів обох статей 56 (29 чоловіків та 27 жінок). Сам хутір розташований по праву сторону транзитної дороги з міста Миколаєва в німецьку колонію Вормс.

Звернемося до матеріалів, що містяться у Російському державному архіві давніх актів, а саме у фонді №1354, Опис 580, Частина 2, Плани дач Генерального та Спеціального межуванння Губернії Херсонській, повіт Одеський. Зокрема у ньому зазначається що у 1867 році було проведено межування колонії Гальбштадт землі, навколо котрої купили вихідці з колонії Карлсруе та інших сусідніх колоній Березанського колоніального округу між 1861-1865 роками.

За селом закріплено 3000 десятин землі з них усі 3000 зручна для землеробства земля.

Щодо картографічних видань, то перша відносно детальна карта, що подає нам відомості про населений пункт, датується 1869 роком. Це трьохверстова карта Генерального штабу Російської імператорської армії.

Згідно з нею в селі з все тією ж подвійною назвою хутор Голіков (Булгарка) нараховується 41 двір, також позначений великий сад у південній частині села.

Щодо цікавого то навколо населеного пункту позначено три вітряні млини та один кам’яний млин. Поруч з селом на захід від нього розташовується корчма.

У 1888 році в колонії нараховується 175 чоловіків та 142 жінки.

Наступне друковане джерело що повідомляє нам про існування села «Список населених місць Херсонської губернії на 1896 рік» виданий херсонським статистичним комітетом. Згідно з ним Гальбштадт (Болгарка) німецька колонія при річці Солонисі має 34 двори, 267 жителів (132 чоловіків та 135 жінок). В колонії розташовується школа що нараховує 36 учнів (23 хлопців та 13 дівчаток) та корчма.

Між 1863 та 1869 роком році в селі засновано церковно-приходську школу, в 1903 році в ній навчалося 44 учні. Навчав їх 1 учитель. В 1923 р. школа була переведена на баланс держави, в ній навчаються вже 80 дітей. В 1929 році в школі нараховувалося 3 класи з 48 учнями в них та 1 учителем.

1893 року в колонії збудовано католицький храм в ім’я святого Антонія Падуанського. Спорудження будівлі відбувалося на кошти місцевих жителів. Освячений храм Єпископом Йосипом Кеслером 17 травня 1910 року.

За спогадами місцевих жителів архітектор, який керував будівництвом храму наказав викопати яму під фундамент, заповнити її негашеним вапном та від кожного двору приносити щонеділі десяток яєць та всі кістки, які назбираються за тиждень та кидати це все до ями. Потім на цьому розчині звели церкву і досі він тримає каміння так, що їх не можна розділити. Каміння ламається, але розчин тримається. Побудований костел із пиляного вапняку. Як уже було сказано вище, церкву освятили у 1893 році. Спочатку храм належав до приходу Карлсруе (Степове), а з 1915 року до приходу Шенфельд (Кринички).

Церква діяла безперервно до 1929 року, коли була закрита за рішенням ВУЦВКу, і почала використовуватися як клуб, пізніше – як склад місцевим колгоспом імені Е. Тельмана. Через пил від зерна та дію атмосферних явищ в церкві майже повністю стерлися розписи. Залишки їх можна бачити лише в кількох місцях, і лише у верхній частині церкви.

Зараз храм знаходиться в стані руйнації. Майже знищена покрівля, замуровані вікна та вхід, яким користувалися при проведенні служб, натепер входом служать ворота, які мабуть видовбали та встановили ще в ті далекі 30-ті роки ХХ століття.

Будівля занесена до переліку архітектурних пам’яток Миколаївського району. Автор внесення костелу до списку О.І. Тищенко.

Щодо промислово-економічного розвитку колонії перед Першою світовою війною потрібно зазначити, що в колонії розміщувався Пивоварний завод Південноросійського акціонерного товариства, також в селі розміщувався пивний склад, що належав Кемпе Матильді. Крім цього в селі діяв млин, господарем котрого був Ральф Ванер та один магазин «бакалея та табачний», котрим володів Франц Бер.

У «Списку населених місць Херсонської губернії», виданому у 1917 році, село іменується Катюшено (Гальбштадт), на його території розташовується 67 особистих господарств. Жителів 534 з них 201 чоловік та 333 жінки. Згідно з примітками в тексті управління селом здійснюється через збори общини. Найближча поштово-телеграфна станція в селі Софієвка (Шенфельд, Кринички).

В роки національно-визвольних змагань українського народу 1917-1920 років в колонії життя йшло своїм не плинним ходом. Є лише невеликі згадки про грабунки червоних влітку 1919 р., наслідком чого стало об’єднання колонії Гальбштадт з колоніями Шенфельд, Штейнберг та Петрівка в один район самооборони.

В 1920 роки на півдні України часто змінювалися адміністративні кордони, через це Гальбштадт опинявся то в Миколаївській області то в Одеській, то належав до Варварівського то до Карл-Лібкнехтівського (Ландауського) районів. Щодо сільських рад то поселення належало то до Новогригорівської то до Шенфельдської сільської ради, доки в 1926 році не було утворено власне Гальбштадську сільську раду, головою якої стає Штикар Г.Ф., секретарем Бауер М.М.

27 березня 1924 року створено кооперативне товариство «Зоргін». Воно об’єднувало 94 пайщики, займалося постачанням товарів різного роду: мануфактура, бакалія, галантерея, хлібне вино та інші товари. Проводить заготовку сільськогосподарської продукції. Головою правління був Гергард Р.Я, члени правління Мец В.Я, Штурн С.Я.

У період з 1930 по 1933 рік в колонії було створено колгосп імені Е.Тельмана. Він поєднував 147 господарств, в котрих нараховувалося 593 особи, з них 288 працездатних та 58 осіб підлітки у віці 12-16 років. За колгоспом закріплено 3 200 гектарів землі, в тому числі ріллі 2 456 га, сад та город 32 га, пасовиська 647 га, виноградник 32 га, в особистому користуванні колгоспників 65 га. Головою правління колгоспу був Микола Максимович Баштовий. Голова ревізійної комісії Кирило Михайлович Кириленко. Бухгалтер Каспар Каспарович Ванер.

Село було окуповане 10 серпня 1941 року німецькими військами та перейшло до румунської зони окупації під назвою губернаторство Трансністрія. В роки війни в колонії розташовувався один із загонів самооборони, на котрий опирався штаб команди СС «Р», що містився в колонії Ландау (сучасна Широколанівка Веселинівського району). До обов’язків загону входило підтримувати порядок в колонії, слідкувати за виконанням сільгоспробіт та виявлення осіб, що не були жителями колонії до війни, останній пункт зокрема майже завжди ігнорувався.

Звільнення села почалося в ніч на 27 березня, коли частини 152-ї Дніпропетровської стрілецької дивізії переправилась через річку Південний Буг в районі сіл Гальбштадт, Кринички, Новогригорівка.

Після війни почалася відбудова села та колгоспу. На початку 1950-х в господарстві колгоспу нараховувалося 100 корів, близько 3000 свиней та понад 1000 овець. Окремою гордістю працівників був збережений в роки війни сад та новостворена пасіка. Діяла городня бригада.

У 1957 році колгосп на правах відділку увійшов до складу радгоспу «Криничанський». В період з кінця 1960-х по 1980-ті роки в селі було відкрито магазин, клуб, створено бібліотеку, почав діяти ФАП.

У 1998 р. земля радгоспу була розпайована. Нині в селі діє ФАП та клуб, працює магазин. Ведуться роботи з газифікації села. Діти села відвідують школу в сусідніх Криничках, школа в самому селі була зачинена в 2007 році.