Joukkue perustettiin vuonna 1911. Jalkapallossa TsSKA voitti Neuvostoliiton mestaruuden yhteensä seitsemän kertaa (1946, 1947, 1948, 1950, 1951, 1970 ja 1991), Neuvostoliiton cupin viidesti (1945, 1948, 1951, 1955 ja 1991), Venäjän mestaruuden kuudesti (2003, 2005, 2006, 2013, 2014 ja 2016), Venäjän cupin seitsemästi (2002, 2005, 2006, 2008, 2009, 2011 ja 2013) sekä Venäjän supercupin neljästi (2004, 2006, 2007 ja 2009).
Lisäksi kaudella 2004–2005 TsSKA voitti jalkapallon UEFA Cupin peittoamalla finaalissa Sporting Lissabonin maalein 3–1. Näin siitä tuli Venäjän ensimmäinen jalkapallon eurocup-tittelin voittanut seura.
Lempinimi ”hevoset” juontuu seuran ensimmäisestä harjoituskeskuksesta, jossa pidettiin Jusupov-aatelissuvun talleja. Kyseinen aatelissuku oli yksi vauraimmista Venäjällä, ja se omisti muun muassa vuonna 1917 400 km² maata, josta osa oli viljelty tai tehdaskäytössä. Jusupov-suku oli myös sekaantunut Grigori Rasputinin murhaan.