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.