Klub je osnovan 1937. godine pod nazivom Lokomotiva Krasnojarsk i učestvovao je jednu sezonu u Klasi D. U 1957. godini klub je reformiran i nastupao je u Klasi B zoni dalekog istoka. Klub je 1968. godine promenio ime u Rasvet a ponovo 1970. godine u Avtomobilist. Opet menjaju ime 1991. godine u Metalurg, a februara 2010. postaju Metalurg-Jenisej (formalno, Metallurg je isključen iz lige a novi nezavisni klub Metalurg-Jenisej je primljen u ligu).[2] U 2011. godini klub menja ime u Jenisej.[3] Klub je dobio ime po reci Jenisej, koja protiče kroz Krasnojarsk.
FK Jenisej (ili njegov prethodnik) nikad nije nastupao u prvenstvu Sovjetskog Saveza ili Premijer ligi Rusije sve do sezone 2018/19. Njihov najbolji rezultat u sovjetskom ligaškom sistemu bilo je 2. mesto u grupi 7 Klase B 1959. godine, u ruskom ligaškom sistemu najbolji rezultat ime je 3. mesto u Prvoj ligi u sezonama 2016/17. i 2017/18. Od raspada Sovjetskog Saveza pet puta ispadao u Drugu ligu (treći rang takmičenja), poslednji put 2006. godine. U sezoni 2015/16., Jenisej je zauzeo 16. mesto u Prvoj ligi i trebalo je da ispadne u Drugu ligu, ali FK Smena iz Komsomoljska koja je trebalo da upadne u Prvu ligu, odustala je zbog finansijskih problema a Jenisej je ostao u Prvoj ligi.[4] Na kraju sezone 2016/17., Jenisej je učestvovao u baražu za Premijer ligu, ali su ispali od Arsenala iz Tule zbog pravila gola u gostima (pobedili na domaćem 2:1, izgubili u gostima 0:1). Narednu sezonu 2017/18. Jenisej opet zauzima 3. mesto i učestvuje opet u baražu za Premijer ligu.[5] Uspeli su da pobede FK Anži ukupnim rezultatom 6:4 i obezbedili su promociju u Premijer ligu za sezonu 2018/19. po prvi put u svojoj istoriji.