Основан в 1937 году под названием «Локомотив», тогда же провёл один сезон в группе «Д» («Города Востока»), после чего был расформирован. После дебюта прошло ровно 20 лет, прежде чем красноярцы снова оказались среди участников всесоюзного первенства. С 1957 по 1967 годы «Локомотив» играл в классе «Б». Затем были вторая группа «А» и вторая лига. 

В 1968 году команда меняет своё название и становится "Рассветом". Так команда называлась недолго и уже в 1970 году переименовывается в "Автомобилист" - долгих 20 лет команда выступала под этим названием и в 1991 году становится "Металлургом", в 2010 г. к этому названию приплюсовывается приставка "Енисей" и вот наконец в 2011 году 18 января "Металлург-Енисей" стал просто "Енисеем".

 В Первом дивизионе команда играла в 1992, 1993, 1996, 1999—2002, 2006 годах остальное время — во Втором дивизионе. Лучший показатель в истории выступлений команды в российских чемпионатах — 9 место в Первом дивизионе в 2001 году. Во втором дивизионе в зоне "Восток" команда являлась победителем в 1995, 1998, 2005 и 2010 годах. Тем самым команда в сезоне 2011-2012 будет снова играть в Первом Дивизионе. 

Рекорды и рекордсмены:

 Наибольшее количество игр за команду Юрий Сипкин – около 600 
  Лучший бомбардир за все годыВадим Белохонов – 110
Лучший бомбардир за сезон Сергей Колчин – 22 (1981) 
Самая крупная победа – 10:0 над "Забайкальцем" (Чита) (1961) 
Самая крупная победа на выезде – 6:0 над "Автомобилистом" (Южно-Сахалинск) (1994) 
Самое крупное поражение -  1:11 от "Лады" (Тольятти) в 2002 году.

 Главный тренер: Александр Алфёров