Der Verein wurde im Jahre 1990 als Polihraftechnika Oleksandrija gegründet. 1992 debütierte die Mannschaft in der zweithöchsten ukrainischen Liga (Perscha Liha). 2001 stieg das Team in die ukrainische Eliteklasse (Premjer-Liha) auf. Nach zwei Saisons in der Premjer-Liha ging der Verein bankrott. 2003 erfolgte die Umbenennung in FK Oleksandrija. Den heutigen Vereinsnamen trägt der Verein seit 2004. Im gleichen Jahr wurde ein Neuanfang in der dritthöchsten ukrainischen Liga (Druha Liha) gestartet. Nach zwei Spielzeiten stieg die Mannschaft im Jahre 2006 in die zweitklassige Perscha Liha auf. 2011 wurde die Meisterschaft der Perscha Liha gewonnen und der damit verbundene Aufstieg in die Premjer-Liha geschafft. Nach nur einer Saison in der Premjer-Liha und dem 16. und letzten Platz spielte der PFK Oleksandrija 2012/13 wieder in der Perscha Liha. 2015 gelang der erneute Aufstieg in die höchste ukrainische Liga. Die erste Saison, in der der Verein wieder in der Premjer-Liha spielte, beendete er auf Tabellenplatz sechs und qualifizierte sich somit für die UEFA-Europa-League-Qualifikation.
Die Saison 2024/25 war für den FC Oleksandrija eine herausragende Spielzeit, in der die Mannschaft erstmals den zweiten Platz in der ukrainischen Premjer-Liha erreichte: hinter Dynamo Kiew, aber noch vor Schachtar Donezk.
Serhij Kusmenko
Hajduk Split
Astra Giurgiu
BATE Baryssau
VfL Wolfsburg
KAA Gent
AS Saint-Étienne
FK Partizan Belgrad
Leonid Burjak (2012)