Новотроицкое основано на месте бывшего аула Сарабулат крестьянами-беглецами из разных губерний России и Украины. Первое письменное упоминание о ауле относится к началу XIX века. После переселения в 1860-1861гг. части ногайцев, которые кочевали в приазовских степях, в Турцию, опустело 96 аулов. Царское правительство принимало срочные меры, чтобы заселить эти земли. В начале 60-х годов XIX в. в Сарабулате поселились государственные крестьяне из Черниговской губернии и 30 семей из села Агайманы Мелитопольского уезда. Сюда прибывали новые группы переселенцев и население быстро росло. Впоследствии название Сарабулат исчезает и в официальных документах село называется Новотроицким, хоть два параллельные названия еще сохранялись почти до 1917 года.
В 1860-е годы на месте аула Сарабулат возникло село Ново-Троицкое, в дальнейшем ставшее центром Ново-Троицкой волости Днепровского уезда Таврической губернии.
По состоянию на 1886 год в селе проживало 1548 человек, насчитывалось 256 дворов, был молитвенный дом, школа, 3 лавки. Ежегодно проводилось 2 ярмарки.
В 1862 году Новотроицкое стало волостным центром и входило в состав Днепровского уезда. Жители села в основном занимались земледелием и овцеводством, а небольшая часть - различными ремеслами.
В 1888 году в селе открыта земская больница на 50 коек, которая обслуживала население всей волости. Долгое время здесь работал один врач, а с 1903 года штат пополнился еще тремя фельдшерами и акушеркой.
О низком состоянии образования свидетельствует тот факт, что в начальной школе 1884 обучалось только 42 мальчика и 15 девочек.
Накануне первой мировой войны Новотроицкое было уже большим селом, где проживало более 3 тыс. человек. Здесь размещались волостная управа, частные лавки, аптека. Жители страдали от недостатка воды. Поэтому село поражало бедностью зеленых насаждений. В апреле 1918 года Новотроицкое захватили австро-германские войска. В августе 1919 года деникинцы захватили деревню. 30 октября 1920 46-я стрелковая дивизия 4-й армии вместе с частями Первой Конной армии, наступавшими со стороны Каховского плацдарма, окончательно освободили село.
В январе 1918 года в селе была установлена Советская власть.
В 1923 году между Новотроицким и Геническом был подписан договор о дружбе. В 1973 году по случаю 50-летия этого события уроженка Геническа, астроном Тамара Смирнова назвала именем посёлка открытый ею астероид — (8445) Новотроицкое.
В январе 1932 года началось издание районной газеты.
12 сентября 1941 фашисты оккупировали Новотроицкое. 31 октября 1943 части 10-го стрелкового корпуса 51-й армии 4-го Украинского фронта освободили Новотроицкое от немецко-фашистских захватчиков.
В 1958 году Новотроицкое стало посёлком городского типа.
По состоянию на начало 1974 года здесь действовали птицекомбинат, пищевой комбинат, маслосыродельный завод и комбикормовый завод.
В 1981 году численность населения составляла 11,2 тыс. человек, здесь действовали птицекомбинат, маслосыродельный завод, завод по производству комбикорма и мясокостной муки, пищевкусовая фабрика, управление эксплуатации оросительных систем, райсельхозтехника, райсельхозхимия, межколхозная строительная организация, комбинат бытового обслуживания, три общеобразовательные школы, музыкальная школа, спортивная школа, больница, поликлиника, Дворец культуры, кинотеатр, три библиотеки и краеведческий музей.
В 1989 году численность населения составляла 12 545 человек.
В октябре 1992 года Новотроицкая пищевкусовая фабрика (ранее входившая в производственное объединение «Продтовары») была передана в коммунальную собственность.
В мае 1995 года Кабинет министров Украины утвердил решение о приватизации находившихся в посёлке мясокомбината, комбикормового завода, райсельхозтехники.
Договор между Херсонской областью и Российской Федерацией от 30.09.2022 года определяет область, включая посёлок городского типа Новотро́ицкое, как новый субъект в составе Российской Федерации
