Málagako lehenengo futbol taldea, Málaga Football Club, 1904ean jadanik sortua izan zen. 1909an izena aldatu zuen F.C. Maagueño bihurtuz, baina 1915an taldea bitan zatitu zen eta atera zirenek berriz ere Málaga F.C. izena hartu zuten. Bi taldeen artean lehia handia izan zen harik eta 1933an elkartu eta Club Deportivo Málaga eratu zuten arte. 1941ean inauguratu zuen gaur egungo La Rosaleda estadioa. 1948an Club Atlético Malagueño sortu zen Club Deportivoren filiala izateko. Urte horretan gainera lehen mailan debuta egin zuen Malagak.
50. eta 60. hamarkadatan gora etabehera ibili ondoren, 1969-70 denboraldian Antonio Rodríguez López presidente aukeratua izan zen Jenő Kálmár entrenatzaile hungariarraren eskutik bost urte egin zituen jarraian lehen mailan, bi aldiz zazpigarren gelditu eta Zamora Sari bat ere jaso zuen. 1973an kopako final erdiak jokatu zituen baina Bilboko Athletic Klubak utzi zuen finaletik kanpo. 1975ean maila galdu zuen eta pare bat aldiz igo bazen ere gainbehera iritsi zitzaion taldeari.
80. hamarkada maila apalean ibili ondoren 1990 urtean bigarren B mailaraino jeitsi zen. 1992an diru arazoak zirela eta Club Deportivo Málagak desagertu beharra izan zuen eta filiala bihurtu zen talde nagusi Málaga Club de Fútbol izen berriarekin. 1992-93 denboraldi hartan taldea hirugarren mailan ari zen jokatzen eta 1999 arte ez zuen lortu lehen mailara igotzerik. Indar handiarekin itzuli zen ordea, lehen urtean hamabigarren, bigarrenean zortzigarren eta 2002an UEFA Intertoto Kopa irabaztea lortu zuen. Hurrengo denboraldian UEFA Kopan hartu zuen parte eta final laurdenetaraino iritsi zen. Berriz ere krisi ekonomikoa pairatu zuen eta 2006an maila galdu ondoren bi denboraldi egin zituen Bigarren mailan.
2008-09 denboraldian berriz lehen mailan aritu zen eta "errebelazio taldea" izan zen, 8. postua lortuz, baina ia bukaerararte UEFArako postuetan ibiliz. 2010ko ekainaren 11an Abdullah ben Nasser Al Thani jeke arabiarrak taldea erosi zuen eta nabarmen indartu ondoren talde konpetitiboa bihurtu da. Manuel Pellegrini du entrenatzaile eta Ruud van Nistelrooy aurrelari. Liga bikaina egin ondoren laugarren gelditu zen, bere historiako posturik onena, eta hurrengo denboraldiko UEFAko Txapeldunen Ligarako sailkatu zen.
2013-14 urtean ez zuen dizdira handirik izan eta 11. egin zuen. 2014-15 denboraldirako Javi Gracia entrenatzailea fitxatu zuen eta denboraldi ia osoa 7. postuan egin ondoren (Europarako sailkatzeko postua) azken partida kaskarren ondorioz 9. postuarekin konformatu behar izan zuen. 2015-16 denboraldian zehar apalago ibili den arren azkenean 8. postua eskuratu du. 2016-17an hiru entrenatzaile izan zituen eta amaieran maila bikaina erakutsi zuen arren azkenean 11. postuarekin konformatu behar izan zuen. 2017-18 okerrago hasi zen eta bost jardunaldi faltan matematikoki jeitsi zen. 20 puntu baino ez zituen lortu denboraldian.
Hurrengo denboraldietan gainbeheran jarraitu du eta 2022-23an maila galdu zuen. 2023-24an Bigarren mailara itzuli zen play-offak jokatu ondoren.