The club was founded in 1975 as Trud Krasnoyarsk (Template:Lang-ru, "labour"), but in 1978 was renamed Sibtyazhmash Krasnoyarsk (Template:Lang-ru). It took its current name on 12 April 2000. STM is an abbreviation for Sibtyazhmash ("Siberian Heavy Machinery", a local firm), while the Enisei is the river that flows through Krasnoyarsk. In the 2008 season the team finished in third place in the Russian championship. The club competed in the European Rugby Challenge Cup for the first time in 2015–16 and have qualified for the 2016–17 competition.