Als Gründungszeitpunkt der Hauptstadt der Insel wird die Eroberung durch die Römer im Jahr 123 v. Chr. angesehen. Möglicherweise erbauten die Besetzer die Stadt an der Stelle einer ehemaligen Talayotsiedlung, die an der weitesten Bucht der Insel lag. Bisher wurde jedoch kein Indiz gefunden, das auf eine frühere Siedlung schließen lässt.

Die neue Stadt erhielt den Namen Palma. Heute ist wenig über diese Epoche bekannt, die nur schwer zu erforschen ist, da die Reste der Römerstadt unter dem alten Kern der Stadt im Almudaina-Viertel begraben sind. In den Straßen dieses Stadtteils ist auch heute noch eine Art römische Präsenz zu spüren, die der Schriftsteller Llorenç Villalonga seinerzeit folgendermaßen beschrieb: „Ein ehrwürdiges, nobles und stilles Viertel mit engen Gassen und weitläufigen, unbewohnt scheinenden Wohnhäusern.“

Trotz allem haben die in jüngster Zeit durchgeführten Untersuchungen viel Information zu Tage gefördert. Einer der interessantesten sichtbaren Überreste ist der untere Teil des Bogens an der Almudaina-Straße, der einst zu einem Stadttor der römischen Befestigung gehörte. Reste dieser Stadtmauer, die noch bis ins 13. Jh. intakt war, sind im Garten des Bischofspalais, im Inneren des Hauses Can Bordils (Calle de la Almudaina Nr. 9) und in der Trennwand zwischen den Häusern der Straßen Morey und Zanglada zu sehen (Ein unverputzter Rest befindet sich im Hof des Gebäudes an der Calle Morey Nr. 14). Nach dem Niedergang des Römischen Reiches fiel die Stadt einem langsamen Verfall anheim, der mit der Eroberung zu Beginn des 5. Jh. durch die Mauren ein Ende fand. Die neue islamische Macht baute den alten Stadtkern wieder auf und vergrößerte ihn. Zentralen Sitz ihrer Machtausübung wurde die Almudaina-Festung, die durch eine Mauer, deren Verlauf der früheren römischen Stadtmauer entspricht, von der restlichen Stadt abgetrennt war. Die Stadt erhielt den neuen Namen Medina Mayurqa und ihre Einwohnerzahl wuchs schnell auf 20 000 an. Der Verlauf der neuen Stadtmauer wurde Anfang des 12. Jh. fertig gestellt und später keinen Veränderungen mehr unterworfen.

1114-1115 zerstörte der Überfall der Katalanen und Pisaer die Medina, die von den Almoraviden wieder aufgebaut wurde. Während des 12. Jh. war die Stadt eine wichtige Handelsdrehscheibe, deren Position durch die Abkommen mit den Republiken von Pisa und Genua noch gefestigt wurde. Die Besetzung durch die Almohaden erfolgte 1203 und war allem Anschein nach nicht übermäßig grausam. Der Handelsverkehr wurde kaum davon beeinträchtigt und konnte bis zur Übernahme durch die Katalanen im Jahr 1229 ungehindert fortgesetzt werden. Die katalanische Besetzung erfolgte nach einer dreimonatigen Belagerung der Stadt. Das christliche Lager befand sich im Norden der Stadt zwischen der Stadtmauer und einer Stelle, die heute als La Real bekannt ist. Von der Blockade sind viele blutige Einzelheiten bekannt. So hängten die Mauren ihre christlichen Gefangenen lebendig an die Mauer, um mit ihren Körpern die Steinwürfe ihrer Glaubensgenossen gegen die Mauer abzufangen. Wie durch ein Wunder wurde jedoch keiner der Gefangenen von den Steinen getroffen. Als Antwort darauf katapultierte König Jaime I. Dutzende abgeschlagene Maurenköpfe in die Stadt. Am 31. Dezember drangen die Truppen des Königs Jaime durch einen in die Medina Mayurqa ein. Dazu nutzten sie einen Mauereinbruch bei dem damaligen Bab al-Kofol Tor, das sich etwa dort befand, wo die heutige Straße Sant Miquel auf den Stadtring Avingudes trifft.

Der Einfall der katalanischen Truppen war außergewöhnlich grausam und führte zur Auslöschung des größten Teils der maurischen Bevölkerung, die entweder getötet wurde oder floh. Viele der Flüchtlinge verließen die Insel endgültig, andere hielten sich in den Bergen versteckt. Selbst das Schicksal des damaligen maurischen Herrschers Abu Yahya ist unklar. König Jaime hatte gedroht, ihn bei seiner Gefangennahme am Bart umher zu schleifen, was als besonders entwürdigend galt. Die besiegte Bevölkerung wurde durch neue Siedler vor allem aus Katalonien ersetzt. So wurden zumindest die demographischen Lücken gefüllt, die durch das Verschwinden der ehemaligen Bevölkerung entstanden waren. Abgesehen von den Menschen verschwand jedoch auch das islamische Erbe aus der Stadt. Die Moscheen wurden zu Kirchen umgebaut oder abgerissen und die maurische Atmosphäre der Wohnviertel wich einer andersartigen Stadtanlage, obwohl die Straßenverläufe weitgehend erhalten blieben.

Während sich das städtische Leben wieder normalisierte, begann der Wiederaufbau der durch die Belagerung stark beschädigten Stadtmauern. Bis ins 17. Jh. hinein bestand die Mauer unverändert und wurde dann durch eine Bewallung ersetzt, deren Linienführung weiterhin im wesentlichen den arabischen Plänen entsprach. Die neue Befestigung stand mit den entsprechenden Toren bis zu ihrer in mehreren Phasen vorgenommen Abtragung im 19. und Anfang des 20. Jh. Heute verläuft dort die Ringstraße Avingudes, die den alten Stadtkern eingrenzt, hinter dem das moderne Palma beginnt.

Zur gleichen Zeit wurde auch mit dem Bau der Kathedrale und zahlreicher Kirchen begonnen, die das Stadtbild der ehemals islamischen Medina im 13., 14. und 15. Jh. entscheidend veränderten. Diese langsame Zerstörung des maurischen Erbes – trotz der Beibehaltung der Straßenführung und nur leichter Veränderung des Wassersystems – kulminierte 1403 in der großen Überschwemmung des Riera-Flusses, die hunderte Wohnhäuser und tausende Menschen mitriss. Zahlreiche Überbleibsel der Maurenzeit sowie gotische Bauwerke aus der Zeit nach der Rückeroberung verschwanden in den Fluten. Der Fluss durchzog die Stadt etwa dort, wo heute die Straßen Rambla und Born verlaufen, bis er 1615 umgeleitet wurde.
Aus administrativen Gründen wurde die umgetaufte Stadt Mallorca (wörtliche Übersetzung ins Spanische von Madina Mayurqa) in die fünf Pfarrbezirke Sant Miquel, Santa Eulalia, Santa Creu, Sant Nicolau und Sant Jaume aufgeteilt. Aus ihnen bildeten sich die alten Stadtviertel heraus, die sich jeweils durch unterschiedliche Funktionen auszeichneten. Um die Kirche Santa Creu herum siedelten sich die Fischer und Seeleute an, im Drassanes-Viertel (Schiffszeughaus), um die Llonja (Fischbörse) und das Consolat (Seefahrtsgericht) lebten die Kaufleute des Seehandels, in der Nähe der Kathedrale wohnte die Aristokratie und in der Gegend von Llevant die Arbeiter und Handwerker. Diese siedelten die einzelnen Handwerkergremien später in unterschiedlichen Straßen an, die bis heute ihre Namen tragen: Gerreria (Töpfer), Ferreria (Schmiede), Bosseria (Täschner), Capelleria (Hutmacher), Pelleteria (Gerber), Argenteria (Silberschmiede), Cereria (Wachszieher) und die heute in Calle de Jaime II. umbenannte Bastaixos (Warenträger). Dort befanden sich auch die Umschlagplätze für die landwirtschaftliche Produktion wie Pes de sa Palla (Strohwaage), Sa Quartera (Getreidemaß), Banc de s´Oli (Ölbank), Pes de sa Farina (Mehlwaage) etc.

Die Vergrößerung der Stadt innerhalb des Mauerrings erfolgte auf Kosten unbebauter Flächen wie Gemüsegärten, Friedhöfe etc. So wurden z.B. im 14. Jh. das Judenviertel und der Stadtteil Sa Calatrava mit einer gradlinig-rechtwinkligen Straßenführung errichtet.