У ході російсько-турецької війни 1768–1774 рр. Російській імперії вдалося взяти під контроль землі між Дніпром та Південним Бугом. Під час війни на півдні України було збудовано кілька земляних укріплень, що згодом виросли до рівня значних населених пунктів.
Навесні 1770 року під час підготовки до Бендерського походу на лівому березі Синюхи при її впадінні в Південний Буг за розпорядженням генерал-аншефа П. І. Паніна було збудовано укріплення, що отримало назву Катерининський шанець. Ймовірно, що твердиня була зведена на місці Орловського шанцю, зведеного у ході російсько-турецької війни 1734–1739 років. Саме через це твердиня в історичних дослідженнях має подвійну назву – Орловський або Катерининський шанець.
Фортецю було збудовано під керівництвом генерал-майора В. П. Мусіна-Пушкіна. Це було земляне укріплення правильної шестикутної форми з шістьма бастіонами та двома в’їздними воротами (західними й східними). Ворота були прикриті равелінами. Фортеця була обведена сухим ровом. На її території були облаштовані казарми для гарнізону та провіантські магазини (склади). У 1770 році твердиня відігравала роль тилової бази Другої армії генерал-аншефа П. І. Паніна під час її походу в Молдавію. Одночасно з фортецею поряд з нею почало формуватися поселення, яке 1781 року отримало статус міста і назву Ольвіополь.
1 травня 1919 року Ольвіополь було перейменовано на Первомайськ з одночасним приєднанням до його складу поселень-супутників – Голти та Богополя. Нині це районний центр Первомайського району Миколаївської області.
Катерининська фортеця до сьогоднішнього дня не збереглася. Вона була розпланована у 1840-х роках.