Sowjetunion

Die Mannschaft wurde am 12. April 1942 gegründet. Am 30. Juli 1944 debütierte sie im Pokal der UdSSR. Das erste Match in der ersten sowjetischen Fußballliga spielte Krylja Sowetow am 21. April 1946 in Alma-Ata. Das Team spielte zwischen 1946 und 1969 bis auf zwei Jahre durchgehend in der höchsten Spielklasse der Sowjetunion, stieg dann jedoch ab und blieb bis 1980 mit Ausnahme von vier Jahren Ende der 1970er Jahre zweitklassig. 1980 erfolgte sogar der Abstieg in die drittklassige Wtoraja Liga, wo sich die Mannschaft bis auf die Spielzeiten 1985 und 1987 bis zum Ende der UdSSR aufhielt. Insgesamt nahm Krylja Sowetow an 48 sowjetischen Fußballmeisterschaften (darunter 26 in der höchsten Spielklasse) und 43 Pokalaustragungen teil.

Russland

Die Mannschaft aus Samara war nach dem Zusammenbruch der Sowjetunion eines der Gründungsmitglieder der neugeschaffenen russischen Obersten Liga. In der Saison 1992 belegte das Team in der Abstiegsrunde den 14. Tabellenplatz und entging knapp dem Abstieg.

Ihre beste Saison spielte die Mannschaft aus Samara im Jahre 2004. Mit dem dritten Rang wurde die beste Tabellenplatzierung in der russischen Meisterschaft erreicht. Außerdem stand Krylja Sowetow im Finale des nationalen Fußballpokals, das allerdings mit 0:1 gegen den tschetschenischen Verein Terek Grosny im hauptstädtischen Lokomotive Stadion am 29. Mai 2004 verloren wurde.

In der Saison 2012/13 rettete sich der Verein auf den 14. Tabellenplatz (Relegationsplatz). In der Relegation traf Samara auf Spartak Naltschik und sicherte sich mit zwei Siegen den Klassenerhalt. 2014 musste Samara erneut in die Relegation gegen Torpedo Moskau, unterlag dem hauptstädtischen Club und stieg zum ersten Mal in seiner Geschichte in die zweitklassige 1. Fußball-Division ab. Im Juni 2014 übernahm der Belgier Franky Vercauteren den Chef-Trainerposten bei Krylja Sowetow. Einen Spieltag vor dem Ende der Saison 2014/15 sicherte sich Krylja Sowetow den Wiederaufstieg in das russische Oberhaus.

Am letzten Spieltag der Spielzeit 2016/17 rutschte Krylja in die Abstiegszone der Tabelle und stieg somit zum zweiten Mal ab. Daraufhin wurde im Juni 2017 der Russe Andrei Tichonow als neuer Chef-Trainer verpflichtet. Ein Spieltag vor dem Ende der Saison 2017/18 sicherte sich der Verein den sofortigen Wiederaufstieg in die Premjer-Liga. In der Saison 2018/19 rettete sich der Verein auf den 13. Tabellenplatz (Relegationsplatz). In der Relegation traf Samara auf FK Nischni Nowgorod und sicherte sich nach 3:1 und 0:1 den Klassenerhalt.