Initially, FC Shakhtar Shakhtarsk was created in 1984 at the State Production Association "Shakhtarskantratsyt" out of local miners' football teams of Vinnitska Mine and Postnykivska Mine.

In 1992 the club was admitted to the Ukrainian Transitional League (third division) from which it was relegated after the first season.

In 1992–93 Prometei even though placing sixth gained a promotion to the Second League after FC Antratsyt Kirovske withdrew from competitions.

In 1995 the club changed its name again to Shakhtar after it was returned under the sponsorship of the Shakhtarskantratsyt.

Next year the club changed its name again to FC Avanhard Shakhtarsk under which it competed until 2011.