A csapat megalapítása előtt is voltak már a városban egyéb, kisebb egyesületek. A CD Málaga két klub, az 1904-ben alapított Málaga Foot-ball Club és a nyolc évvel később létrejött Fútbol Club Malagueño egyesülése után jött létre. 1941-ig CD Malacitano volt az új csapat neve.
Bár első szezonját a harmadosztályban töltötte, egy év után rögtön feljutott, és később is összesen csak négy szezont szerepelt itt. Története során nagyrészt az első- és másodosztály között ingázott, legjobb eredménye az első osztályban két hetedik hely volt a hetvenes évekből.[1]
1992-ben, a másodosztályból való kiesés után megszűnt. Utódja a Málaga CF.
A Málaga 1961 és 1983 között saját barátságos labdarúgókupa-sorozatot indított Trofeo Costa del Sol néven. Érdekesség, hogy a kupát kétszer magyar csapat is elnyerte, 1970-ben a Vasas, kilenc évvel később pedig a Ferencváros.[2]
2003-tól a Málaga CF ismét életre hívta a sorozatot.