Клуб је основан 1937. године под називом Локомотива Краснојарск и учествовао је једну сезону у Класи Д. У 1957. години клуб је реформиран и наступао је у Класи Б зони далеког истока. Клуб је 1968. године променио име у Расвет а поново 1970. године у Автомобилист. Опет мењају име 1991. године у Металург, a фебруара 2010. постају Металург-Јенисеј (формално, Металлург је искључен из лиге а нови независни клуб Металург-Јенисеј је примљен у лигу).[2] У 2011. години клуб мења име у Јенисеј.[3] Клуб је добио име по реци Јенисеј, која протиче кроз Краснојарск.
ФК Јенисеј (или његов претходник) никад није наступао у првенству Совјетског Савеза или Премијер лиги Русије све до сезоне 2018/19. Њихов најбољи резултат у совјетском лигашком систему било је 2. место у групи 7 Класе Б 1959. године, у руском лигашком систему најбољи резултат име је 3. место у Првој лиги у сезонама 2016/17. и 2017/18. Од распада Совјетског Савеза пет пута испадао у Другу лигу (трећи ранг такмичења), последњи пут 2006. године. У сезони 2015/16., Јенисеј је заузео 16. место у Првој лиги и требало је да испадне у Другу лигу, али ФК Смена из Комсомољска која је требало да упадне у Прву лигу, одустала је због финансијских проблема а Јенисеј је остао у Првој лиги.[4] На крају сезоне 2016/17., Јенисеј је учествовао у баражу за Премијер лигу, али су испали од Арсенала из Туле због правила гола у гостима (победили на домаћем 2:1, изгубили у гостима 0:1). Наредну сезону 2017/18. Јенисеј опет заузима 3. место и учествује опет у баражу за Премијер лигу.[5] Успели су да победе ФК Анжи укупним резултатом 6:4 и обезбедили су промоцију у Премијер лигу за сезону 2018/19. по први пут у својој историји.