«Мальорка», старейший клуб Балеарских островов, был основан Адольфо Васкесом в 1916 году под названием Junta Directiva del Alfonso XIII FBC в честь правившего тогда короля Альфонса XIII. Первым стадионом клуба был «Буэнос-Айрес», открывшийся 25 марта того же года матчем с «Барселоной» в котором «Мальорка» проиграла со счётом 0:8. Через год клуб сменил название на Real Sociedad Alfonso XIII, но в 1931 году по политическим причинам был переименован в Club Deportivo Mallorca. Приставка Real была добавлена в 1949 году.
В 1917 году клуб начал выступать в чемпионате Каталонии и в первом же сезоне одержал победу в финале, проходившем в Барселоне, над «Палафружелем» со счётом 3:1.
В 1919 году в структуру клуба вошла команда по велоспорту.
В 1960 году «Мальорка» впервые попала в Примеру под руководством Хуана Карлоса Лоренсо. Четыре года спустя команда вернулась в высший дивизион. Тренером был Сесар Родригес. Вылетев из Примеры, клуб, которым руководил Хуанчо Форнерис, снова стал участником главного чемпионата страны в 1969 году.
Автором первого гола «Мальорки» в Примере стал Хуан Фортеза, единственный футболист, сохранивший своё место в клубе после того, как Хайме Роселло Паскуаль стал президентом. Команда усилилась игроками «Барселоны». В первом сезоне в Примере «Мальорка» финишировала девятой. Тренер и президент покинули клуб. На следующий год команда стала 11-й. В течение нескольких сезонов «Мальорка» то покидала Примеру, то вновь завоёвывала право выступать в ней.
В сезоне 1965/66 клуб вылетел в Сегунду, его покинул многолетний лидер Хуан Фортеза. Его примеру последовали другие футболисты.
К счастью, в 1969 году тренерский дуэт Хуана Карлоса Форнериса и Серхио Родригеса вывел команду в Примеру, однако в первом же сезоне «Мальорка» заняла последнее место, что стало началом самого сложного десятилетия в истории клуба.
В сезоне 1974/75 «Мальорка» покинула Сегунду. За этим последовал вылет из неё в 1978 году. Клуб был на грани исчезновения.
В ноябре 1977 года футболисты «Мальорки» заперлись в раздевалке, требуя выплаты зарплаты. До этого все игроки были выставлены на трансфер, однако ни один клуб не заинтересовался в их услугах.
Тем не менее в сезоне 1979/80 «Мальорка» заняла первое место в Терсере и вышла в недавно созданную Сегунду B, что значительно улучшило состояние клуба.
В начале 80-х клубом стал руководить Мигель Контести. В сезоне 1980/81 команда вышла в Сегунду А. Тренируемая Антонио Овьедо «Мальорка» установила рекордную серию домашних матчей без поражений, не превзойдённую до сих пор.
В сезоне 1982/83 команда в четвёртый раз в истории добилась права играть в Примере. За три недели до окончания чемпионата «Мальорка» уступила «Кастилье» 0:1, однако благодаря победе «Коруньи» вышла в высшую лигу. Впрочем, в первый же год команда вернулась в Сегунду А под руководством Марселя Доминго, где провела два года. Тогда же «Мальорка» впервые подписала игрока из Северной ИрландииДжерри Армстронга.
Сезон 1986/87 в Примере стал невероятно успешным: «Мальорке» не хватило одного очка, чтобы попасть в еврокубки, а годом спустя команда уже не была так хороша. Серра Феррера сменил Люсьен Мюллер.
После вылета команда в очередной раз вернулась в Примеру по итогам сезона 1988/89, победив в стыковых матчах «Эспаньол». Проиграв гостевой матч со счётом 0:1, дома «Мальорка» взяла реванш и победила 2:0 благодаря голам Мигеля Анхеля Надаля и Видаля. Празднования в городе по этому поводу не прекращались до утра.
В сезоне 1990-91, клуб вышел в финал Кубка Испании впервые в своей истории, проиграв в один мяч «Атлетико Мадрид»
В 1997 году на пост главного тренера клуба был назначен аргентинец Эктор Купер. В его первый сезон клуб дошёл до финала Кубка Испании-1998, проиграв по пенальти «Барселоне» после ничьи 1-1 в основное время на стадионе «Месталья». Однако, по причине того, что Барселона так же стала чемпионом Испании, Мальорка стала их соперниками в Суперкубке Испании, обыграв соперников со счётом 3-1 по сумме двух матчей. Два трофея Барселоны так же означали, что Мальорка примет участие в розыгрыше Кубка Обладателей Кубков 1998-99, где они проиграли 2-1 итальянскому «Лацио» на «Вилла Парк» в финале турнира.
В 2013 году главным тренером команды стал Хосе Луис Ольтра, однако «Мальорка» стартовала с трёх поражений кряду, и Ольтру сменил Луис Каррерас. Спустя несколько игр на тренерском мостике появились Хавьер Олаизола и Пеп Аломар.
В следующем году у руля команды встал Микель Солер. Его сменил Валерий Карпин. После пяти побед подряд «Мальорка» поднялась в середину турнирной таблицы, однако вскоре Карпина сменил Утс Клаасен. Команда пополнилась 15 новыми футболистами, в том числе молодыми. Так как большинство из них были свободными агентами, затраты клуба оказались минимальными.
К зиме 2015 года команда снова занимала место в зоне вылета. Новым главным тренером был назначен Пеп Галвез.
4 января 2016 года Роберт Сарвер выкупил большую часть акций клуба. Пепа Галвеза сменил опытный Фернандо Васкес, тренировавший «Мальорку» в 1999 году. Команда сумела сохранить место в Сегунде А благодаря гостевой победе над «Вальядолидом» 3-1.
По итогам сезона 2016/17 года команда выбыла в Сегунду Б.
В сезоне 2018/19 года клуб занял 5-е место в Сегунде и получил право участвовать в стыковых матчах за право попадания в высший дивизион. После победы над «Альбасете» и «Депортиво», «Мальорка» вышла в Примеру.
В сезоне 2019/20 года «Мальорка» потеряла шанс остаться в Примере ещё в предпоследнем туре (Мальорка — Гранада, 1:2) и вновь выбыла в Сегунду[1]
.svg){kind=small}
.svg){kind=small}
