The club was formed in 1991 as Polihraftekhnika Oleksandriya (Ukrainian: Поліграфтехніка Олександрія) at the local polygraph-machine building factory. The establishment of the club was an attempt to return the big football to the city, since the times when the former city's other club, Shakhtar, previously participated in the Soviet Second League.
From 2001–03, PFC Oleksandriya played in the Ukrainian Premier League under the name of Polihraftechnika Oleksandriya, which is 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.
The club renamed itself to Oleksandriya in 2003 and reentered the Professional Football League in 2004 entered the Druha Liha Group B.
The club renamed itself to the current name PFC Oleksandriya in 2006.
Prior to the start of 2014–15 Ukrainian First League season PFC Oleksandriya merged with UkrAhroKom Holovkivka, who were also completing in the Ukrainian First League into one club renaming themselves to FC Oleksandriya. Since the latest merger, the club now claims its heritage of the Soviet miner's team of Shakhtar by adding year of Shakhtar's establishment onto its club shield.