La capital de l´illa té una data de naixement específica: l´any 123 a. C., arran de la conquesta romana. Pot ser que la ciutat fos bastida pels conqueridors a partir d´un anterior emplaçament talaiòtic, que dominaria tota la badia, la més ampla de totes les que hi ha a l´illa. De tota manera, fins ara no hi ha cap indici d´aquest hipotètic nucli anterior.

La nova ciutat fou anomenada Palma. A hores d´ara, el coneixement que en tenim és escàs i mal d´esbrinar, ja que les seves restes romanen al subsòl del nucli antic, concretament sota el barri de l´Almudaina. Aquest encara conserva la traça romana dels seus carrers i manté l´esperit que va descriure al seu moment l´escriptor Llorenç Villalonga: «el barri és venerable, noble i silenciós, amb carrers estrets i cases amples, que semblen deshabitades».

Amb tot, les excavacions que s´han duit a terme als últims anys han aportat nombrosa informació. Una de les restes visibles més importants la constitueix la part inferior de l´arc del carrer de l´Almudaina, que correspon a una porta de la murada romana. D´aquesta murada, que arribà fins al segle XIII, en queden restes al jardí del palau episcopal, a l´interior de Can Bordils (cr. Almudaina, 9) i a la paret mitgera entre les cases dels carrers d´en Morey i Zanglada (per exemple, se´n pot veure una mostra al descobert al pati de l´edifici del carrer d´en Morey, 14). Després de l´extinció de l´imperi, la ciutat entrà en un procés de decadència fins a la conquesta islàmica de principis del segle X. El nou poder musulmà reconstruí i amplià el nucli anterior i hi bastí la seu central del poder, amb l´edificació de la fortalesa de l´Almudaina, separada de la resta de la ciutat per una murada, que aprofitava l´antic traçat murari romà. La ciutat passà a anomenar-se Madina Mayurqa i es va expandir de manera notable, fins arribar a superar els 20.000 habitants. Un nou perímetre de murada la va encerclar, que a principis del segle XII assolí el seu traçat definitiu, el qual ja no va experimentar més canvis.

El 1114-1115 l´atac catalanopisà devastà la madina, que fou reconstruïda pels almoràvits. Al llarg del segle XII, l´activitat comercial de la ciutat fou important, intensificada pels tractats signats amb les repúbliques de Pisa i Gènova, els mercaders de les quals disposaven de les seves pròpies instal·lacions. L´ocupació almohade de 1203, sembla que no excessivament violenta, no destorbà el tràfec mercantil, que continuà fins a la conquesta catalana de 1229.

Aquesta conquesta tengué lloc després de més de tres mesos de setge contra la ciutat. El campament cristià se situà a la part nord de la ciutat, entre la murada i el lloc que avui s´anomena La Real. El setge està farcit d´episodis violents, com quan els musulmans penjaren vius damunt la murada els presoners cristians, perquè rebessin l´impacte de les pedres que llançaven els seus correligionaris contra el mur (miraculosament cap pedra impactà sobre un d´ells) o la rèplica de Jaume I, que féu llançar dins la ciutat dotzenes de caps dels musulmans morts. Finalment, el dia 31 de desembre, les tropes del rei En Jaume entraren dins madina Mayurqa, aprofitant l´enfonsament d´un tros de murada a una de les portes del recinte, concretament la porta de «Bab al-Kofol», situada a l´actual confluència entre el carrer de Sant Miquel i les Avingudes. És famós el crit de guerra amb què el rei esperonava els seus cavallers quan aquests retrocedien, empesos pels assetjats: «Vergonya, cavallers, vergonya!».

L´entrada de les tropes catalanes, violentíssima, comportà l´extinció d´una bona part dels antics pobladors musulmans, que bé foren assassinats o bé fugiren; en aquest últim cas, una part abandonà l´illa i els altres es refugiaren a les muntanyes de l´interior. Fins i tot no se sap res del destí del governant musulmà d´aleshores, Abu Yahya, de qui el rei En Jaume prometé que en aglapir-lo l´estiraria per la barba, fet que tenia un sentit força humiliant. La població vençuda fou substituïda pels nous colonitzadors, majoritàriament catalans, que ompliren en part el buit demogràfic provocat per la desaparició dels anteriors habitants. No només, però, desaparegué la gent sinó la traça islàmica de la ciutat: les mesquites foren convertides en esglésies o enderrocades, la fesomia moresca de les cases donà lloc a una altra tipologia urbana (tot i que a grans trets romangué l´estructura viària), etc.

Mentre la vida urbana es normalitzava, començaren les obres de reconstrucció de les murades, malparades pel setge. Aquestes es mantingueren dempeus fins que al segle XVII foren substituïdes per una nova estructura, que seguia el traçat antic, d´origen islàmic, sense gairebé canvis. La nova murada, amb les seves portes, fou present fins al seu enderrocament, fet en successives etapes, els últims anys del segle XIX i els primers del XX. Al seu lloc, hi ha ara les avingudes, autèntica via de circumval·lació de la ciutat antiga, a partir de les quals arranca el modern eixample de Palma.

Alhora s´inicià l´edificació de la Seu i de les nombroses esglésies i convents que durant els segles XIII, XIV i XV modificaren el paisatge urbà de la ciutat musulmana. Aquest procés de destrucció de la ciutat islàmica —tot i conservar-se el traçat dels carrers i el sistema de distribució de l´aigua, amb retocs—  culminà amb la inundació provocada pel torrent de la Riera el 1403, que destruí centenars de cases i ocasionà uns quants milers de morts, fent desaparèixer molts de testimonis, tant de la dominació islàmica, com del gòtic posterior a la conquesta. Aquest torrent travessava la ciutat per la Rambla i el Born actuals, fins que, a causa de les constants inundacions, fou desviat del seu curs, mitjançant unes obres que s´acabaren l´any 1615.

A efectes administratius, la rebatejada ciutat de Mallorca (traducció literal en català de madina Mayurqa) es dividí en cinc parròquies: Sant Miquel, Santa Eulàlia, Santa Creu, Sant Nicolau i Sant Jaume. A partir d´elles sorgiren els barris antics, caracteritzats per funcions específiques. Entorn de Santa Creu es reuniren els pescadors i mariners; a les Drassanes, prop de la Llonja i del Consolat, els mercaders de la mar; al voltant de la Seu residia l´aristocràcia; i a la part de Llevant es localitzaven les classes treballadores i els menestrals, que més tard es reuniren en gremis per carrers i dels quals encara queden els noms: Gerreria, Ferreria, Bosseria, Capelleria, Pelleteria, Argenteria, Bastaixos (ara anomenat Jaume II), Cereria, etc. Aquí també se situaven les activitats mercantils lligades a la producció rural: Pes de sa palla, Sa quartera, Banc de s´oli, Pes de sa farina, etc., els topònims de les quals encara perduren.

Des d´un punt de vista urbanístic, el creixement es féu intramurs, a partir de la reserva de sòl no edificat (horts, necròpolis...). Així, per exemple, el Call i el barri de sa Calatrava es construïren durant el segle XIV. Cal destacar la regularitat del traçat de les zones urbanitzades de nova planta, cosa que fa pensar en una certa planificació de l´espai. Fora dels murs, l´obra pública més important fou l´inici de la construcció del primer moll de Palma, també iniciat durant el segle XIV, per tal d´apropar a la ciutat les activitats que es realitzaven a Portopí.