A Baleár-szigetek legrégebbi klubját 1916-ban alapította Adolfo Vázquez mérnök. Az újonnan létrejött klub eredeti neve Junta Directiva del Alfonso XIII FBC lett XIII. Alfonz tiszteletére. Az első stadiont, a Buenos Airest ugyanez év március 25-én avatták fel egy FC Barcelona elleni 8–0-s vereséggel. Egy évvel később a klub új neve Real Sociedad Alfonso XIII lett, a ma is használt Club Deportivo Mallorcát 1931-ben vette fel. Ez elé 1949-ben kapta meg a Real (királyi) jelzőt, így alakult ki a ma ismert teljes hivatalos név.
A klub 1931-től eleinte regionális bajnokságokban indult. 1939-ben sikerült feljutnia a másodosztályba, ekkortól a másod- és a harmadosztály között ingázott. 1945-ben lett felavatva a klub új stadionja, az Es Fortí. 1958 és 1960 között egymás után jutott fel előbb a másod-, majd története során először az első osztályba, ám a La Liga-tagság ekkor még csak háromévesre sikerült.
Az 1980-as évektől már legfeljebb csak a másodosztályig esett vissza, 1981 és 1997 között a La Liga és a Segunda División között ingázott. 1997 óta folyamatosan első osztályú tag, ekkor harmadikként zárt a CP Mérida és az UD Salamanca mögött. 2003-ban, amikor a Gregorio Manzano irányította klub kilencedik lett a bajnokságban, sikerült megszereznie első Copa del Rey-trófeáját, öt évvel azután, hogy az előző döntőjét elbukta a Barcelona ellen. 1999-ben érte el legnagyobb nemzetközi sikerét, amikor a KEK utolsó kiírásának döntőjét játszhatta az SS Lazio ellen. A finálé végül az olasz csapat 2–1-es győzelmével zárult.
2008. július 22-én a klub részvényeinek 96 százaléka a kétes hírű brit üzletember, Paul Davidson kezébe került.[1] Davidson később nem tudott érdemben munkálkodni pénzhiány miatt, így 2009. január 15-én a három évvel korábban a klubot már irányító Mateo Alemany lett az elnök.[2]
2010 májusának végén a klub csődöt jelentett,[3] azonban végül nem szűnt meg, ugyanis egy, többek között a korábbi vezetőedző Lorenzo Serra Ferrert és a mallorcai születésű teniszsztár Rafael Nadalt magában foglaló konzorcium megvásárolta az egyesületet.[4][5][6] Ennek ellenére 2010. július 22-én, a nehéz pénzügyi helyzet miatt a Mallorcától megvonták az indulás jogát az Európa-ligában, hiába végzett az előző idényben ötödikként.[7]