The foundational origins of the club are traced in 1904 when the team known as Málaga Football Club played the first matches in the city of Málaga. The rival club Football Club Malagueño, originated soon after, established a competition between both squads until it was decided that both should merge into a sole club, with the physical entity of FC Malagueño being used as basis due to having a wealthier economy and better players. In 12 April 1933, FC Malagueño was renamed to Club Deportivo Malacitano and, in 1934, made its debut in the second level, when the category was expanded from ten teams to twenty-four.
In 1941, the club changed its name once again to Club Deportivo Málaga. After last competing in division three in 1960, the team fluctuated between both major levels of Spanish football, achieving a best position in La Liga in the 1971–72 season and the 1973–74 season, finishing both in seventh position.
CD Málaga folded after the 1991–92 campaign, spent in the second division - being relegated - immersed in overwhelming financial problems. Málaga Club de Fútbol, the former reserve team of the club which was known as Club Atlético Malagueño, managed to elude the folding through a claim of independent autonomy, and became since then the spiritual continuity of CD Málaga and all its line of heir. Málaga CF is currently working into obtaining a legal link to CD Málaga and being officially recognised by RFEF and LFP as the same club.
Between 1961 and 1983, Málaga organised its own summer tournament, the Trofeo Costa del Sol. The hosts won it on three occasions, successively defeating Real Madrid, Red Star Belgrade and Derby County. In 2003, the competition was revived by Club Deportivo's successor, Málaga CF.
In 1976, CD Málaga won a similar summer trophy, the Trofeo Ciudad de La Línea, played in La Línea de la Concepción, near Gibraltar. The triumph arrived after penalty shootout defeats of FC Dinamo Tbilisi and Valencia CF, after 0–0 draws.