1 Mart 2004 yılında yeni takımın varlığı ilk defa Rus yönetimi tarafından bildirildi. FK Moskva, Torpedo-ZIL takımı temellerinde kurulmuş bir takımdır. Takım 2007 yılında Kubok Rossii'de final oynadı.
FK Moskva'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ı Yuri Lujkov genelde bir şapkayla dolaştığı için.)
FK Moskva 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-2009 UEFA Kupası'nda Legia Warszawa'yı eleyerek final turlarına kalmayı başardı.
Not: Uyruk bilgisi futbolcuların FIFA uygunluk kurallarınca oynayabileceği millî takımı gösterir. FIFA kuralları haricinde başkaca uyruğa da sahip olabilirler.
Not: Uyruk bilgisi futbolcuların FIFA uygunluk kurallarınca oynayabileceği millî takımı gösterir. FIFA kuralları haricinde başkaca uyruğa da sahip olabilirler.