1 Mart2004 yılında yeni takımın varlığı ilk defa Rus yönetimi tarafınfan bildirildi. FK Moskova, Torpedo-ZIL takımı temellerinde kurulmuş bir takımdır. Takım 2007 yılında Rusya Kupası'nda final oynadı.
Lakabı
Fk Moskova'ya taraftarlar ve gazeteciler tarafından verilen lakapYurttaşlar 'dır (Rusça: Горожане). Günlük konuşma dilindeki lakabı ise Moskova yönetiminin kulübe sahip olduğunu vurgulamak için Şapkalar olmuştur (Rusça: Кепки). (Moskova Belediye Başkanı Yuriy Luzhkov genelde bir şapkayla dolaştığı için.)
Avrupa'da FK Moskova
FK Moskova Avrupa arenasındaki ilk yılında 2006 yılı Intertoto Kupası'nda 3. tura ulaştı ve ardından Herta Berlin'e elenerek kupaya veda etti. Avrupa arenasında kendini ikinci kez gösteren ekip 2008-2009UEFA Kupası'nda Legia Varşova'yı eleyerek final turlarına kalmayı başardı.