FC Shakhtar Oleksandriya was established in 1948 at the production association "Oleksandriyavuhillya" (Aleksandriaugol). At first the club played at the amateur competitions of the Ukrainian SSR until 1962 when it was accepted to the Class B which was a professional competitions. It played in Class B until the tournament was disbanded in 1971. After that the club returned to the amateurs where it played in 1971-85 and 1988-1990. After 1990 season the club folded.
The club played its games at its own Shakhtar Stadium.
The club was formed on 6 March 1990 as Polihraftekhnika Oleksandriya (Ukrainian: Поліграфтехніка Олександрія) at the local polygraph-machine building factory. The same year the club won the regional football competitions of the Kirovohrad Oblast. At same time in 1990 another Oleksandriya club Shakhtar represented the Kirovohrad region at the republican amateur level. FC Shakhtar Oleksandriya was a club of the Oleksandriyavuhillya coal mine company. At first Polihraftekhinka was leasing the Shakhtar Stadium, while building its own stadium Olimp.
From 2001–03, PFC Oleksandriya played in the Ukrainian Premier League under the name of Polihraftechnika Oleksandriya, which it had since 1991. After the 2003 season the club's administration citing fiscal problems left the Professional Football League and was idle for one season.
In 2004 the president of Polihraftekhnika reestablished the club as PFC Oleksandriya, rejoined the Professional Football League and entered the Druha Liha. At the same time the Oleksandriya city administration created own football club MFC Oleksandriya which also entered the Druha Liha, however, soon thereafter the city's club withdrew from professional competitions.
Prior to the start of 2014–15 Ukrainian First League season PFC Oleksandriya going through some financial difficulties merged with UkrAhroKom Holovkivka who were also competing in the Ukrainian First League into one club and renaming themselves to FC Oleksandriya. The merger saved the Oleksandriya's club from another bankruptcy. Since the 2014 merger under the new manager Serhiy Kuzmenko (former chairman of FC UkrAhroKom), the club now claims its heritage of the Soviet miner's team of Shakhtar Oleksandriya by adding year of Shakhtar's establishment onto its club shield.
In the 2015–16 Ukrainian Premier League season, FC Oleksandriya finished 6th place, earning their best achievement in the Ukrainian top flight yet and qualifying for the third qualifying round of UEFA Europa League, where they will mark their debut in a European competition.
The club plays its games at the Sports Complex "Nika" that was built in place of the old Shakhtar Stadium. At the new stadium Oleksandriya plays since summer of 1998.
Since 1992 Oleksandriya, at that time Polihraftekhnika, was forced to play at another city stadium "Olimp" which is located on western outskirts of the city. FC Shakhtar Oleksandriya denied its city rival to play at its home stadium "Shakhtar" which was located in the center of the city. After Shakhtar Oleksandriya became defunct, its stadium was demolished and on its place was built sports complex "Nika" which was hand over to Polihraftekhnika in 1998.