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. The Germans occupied the city during War War II from 1941 - 1944. A witness recounted of the Germans' occupation: "When they arrived, the German soldiers burned the synagogue near the river and set fire to the Jewish houses. They were terrible. The Jews tried to take the furniture from their houses so it wouldn’t burn."
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.