The city is first mentioned in 1754, as the settlement Usivka (Ukrainian: Усівка, Russian: Усовка). During establishment of the Russian colony of New Serbia in 1754-64, next to the settlement was established encampment (fort) Bechey (after the Serbian city of Bečej) that quartered the 3rd Pandurs company (see Trenck's Pandurs). Since 1784, it has carried the name Oleksandriysk and later Oleksandriya. In 1806-1922, Oleksandriya was a county (uyezd) seat.
A popular place to visit in the town is Oleksandriia's square, known as Lenin Square ("Площадь Ленина"). In the middle of the square there is a statue of Vladimir Lenin, and not far from it an old cinema.