The club was founded in 1937 as Lokomotiv Krasnoyarsk and spent one season in Class D of the Soviet league. In 1957 the club was re-formed and entered the Far East zone of Class B. In 1968 Lokomotiv was renamed Rassvet and, in 1970, Avtomobilist. In 1991 it became Metallurg, a title it held until February 2010 when it was renamed Metallurg-Yenisey (formally, Metallurg was excluded from the league and a new independent club Metallurg-Yenisey was admitted into the league). In 2011, the club was renamed to Yenisey. The club is named after the river of Yenisei, where Krasnoyarsk is located.
Yenisey (or their predecessors) never played in the Soviet Top League or Russian Premier League until 2018. Their best result in Soviet League was a 2nd position in Group 7 of Class B in 1959, while their best result in Russian history is the 3rd position in Russian National Football League in 2016–17 and 2017–18. Since the end of the Soviet Union the club has suffered relegation to the Second Division on five occasions, most recently in 2006. In the 2015–16 season, Yenisey took 16th spot in the FNL and should have been relegated, but one of the third-tier Russian Professional Football League zone winners, FC Smena Komsomolsk-na-Amure, refused to be promoted due to lack of financing, and Yenisey stayed in the FNL. At the end of the 2016–17 season, Yenisey reached the Russian Premier League promotion play-offs, but lost to FC Arsenal Tula on away goals rule (2–1 at home, 0–1 away) and stayed in the FNL. Despite spending a portion of the next 2017–18 season in the top-two direct-promotion spot, by the end of the season Yenisey dropped into 3rd position and qualified for promotion play-offs again. They defeated FC Anzhi Makhachkala 6–4 on aggregate in the promotion play-offs and were promoted to the Russian Premier League for the 2018–19 season for the first time in team's history.