The contemporary club traces its history to 1983 when in Kommunarsk was founded new football club Budivelnyk (Stroitel). The club started out in the championship of Luhansk Oblast. During that time the city top club was Kommunarets which was in synchronization with the former name of Alchevsk – Kommunarsk in the honor of the Paris Commune. Its communist revolutionary spirit can be noticed on the contemporary club's logo. With the fall of the Soviet Union Kommunarets was relegated from the Soviet championship in 1988 and disappeared, while Budivelnyk led by Anatoliy Volobuyev became sponsored by the city's metallurgic factory and were introduced to the Ukrainian SSR championship among physical culture clubs (KFK) for the 1989 season. In 1990 the club placed second in the final tournament and was promoted to the Soviet competitions (1991 Soviet Second League B).
Stal joined the Ukrainian Premier League in 2000–2001 for its tenth season. They finished in the next-to-last place and were relegated back to the Persha Liha where they remained until the 2005–2006 season, for which they and FC Kharkiv achieved promotion back to the Ukrainian Premier League. In 2006–2007 season Stal were relegated back to the Persha Liha, where they played till the end of the 2012–13 season in which they won promotion to the Ukrainian Premier League. But the club refused this promotion because of its Stal Stadium did not meet the requirements of the highest Ukrainian division and the club did not want to play in another stadium because it did see "no point in holding matches in another stadium as most fans of Stal won’t see them".
In 2015, Stal withdrew from all competitions due to the escalating conflict in Eastern Ukraine, with ongoing battles and artillery fired near the playing fields, the club decided it was impossible to continue operating in such conditions.
"Stal" is a popular name in the Soviet culture and stands for "steel" (in English). The name was chosen as the pride for the heavily industrialized region of the country. A derivative of it "Stalin" was carried by the Soviet dictator Joseph Dzhugashvili.
Squad is given according to the club's Official website and PFL Site, as of July 29, 2014. Note: Flags indicate national team as defined under FIFA eligibility rules. Players may hold more than one non-FIFA nationality.