Dels anomenats «Segles obscurs» (s. VI-IX) gairebé no queden restes a Palma,  ni en tota l´illa. Aquestes també són molt reduïdes pel que fa a l´època musulmana (s. X-XIII), tot i que les excavacions dels últims anys han tret a la llum nombrosos vestigis del passat islàmic illenc. Una mostra es troba en el subsòl de l´edifici de Ca la Gran Cristiana, seu actual del Museu de Mallorca (carrer de la Portella, 5), en el qual es conserva en part una casa d´origen musulmà, que data del segle XII, i que fou reocupada en època cristiana al llarg dels segles XIII i XIV. El testimoni arquitectònic més important el constitueixen els anomenats Banys Àrabs (carrer de Can Serra, 7), dels quals només ens ha arribat la sala central, destinada a banys calents, i una estança annexa de planta rectangular i amb volta de canó. Un arc de ferradura dóna accés a la sala principal. La planta d´aquesta sala és quadrada i es troba dividida en dos espais per dotze columnes amb arc de ferradura, paral·leles a les parets. La coberta central és a través d´una cúpula semiesfèrica amb claraboies lobulades, mentre que l´altra ho és amb volta de canó. És possible que aquests banys fossin usats per la comunitat jueva de la ciutat. Tradicionalment, s´ha considerat que foren construïts a final del segle X o principi del segle XI, però una hipòtesi més recent planteja la possibilitat que siguin de principi del segle XII, fets just després de la ràtzia pisanocatalana, aprofitant materials d´edificis afectats per la devastació.

Una altra mostra d´aquell període és l´arc de l´Almudaina, situat al carrer d´aquest mateix nom. Correspon a una porta de l´antiga muralla romana i de l´alcassaba islàmica, tot i que la seva estructura actual és el fruit de transformacions posteriors. Per això, aquesta no correspon a una construcció pròpiament romana ni tampoc musulmana, encara que hi ha elements atribuïbles a l´època islàmica. El més probable és que els seus trets essencials provenguin d´una reconstrucció de la porta romana, feta durant el segle V. De l´època islàmica presenta com a tècnica constructiva la fàbrica conservada sobre les dovelles, mentre que les mènsules que suporten els diferents afegits de les cases veïnades són gòtiques.

Un altre arc, en aquest cas d´origen totalment islàmic, és l´arc de la Drassana Musulmana, ubicat a la confluència actual entre els jardins de L´Hort del Rei i el Parc de la Mar. Donava accés directe des de la mar al moll del palau de l´Almudaina, un petit port privat dels governants musulmans de Mallorca, ja que el port de la madina estava a uns quants quilòmetres de la ciutat, a l´actual Portopí. És un arc semicircular, lleugerament el·líptic, que presenta una ampla llum de 18 metres. El més possible és que dati de la primera època musulmana, durant el període califal cordovès (segle X), i reflecteix bé el poder naval islamicomallorquí d´aquell temps. Durant segles,  aquest arc es mantingué cegat i fou descobert i restaurat el 1961, quan s´enderrocà el quarter de Cavalleria, arran de les obres de reforma de l´Almudaina.

També provinent de l´època islàmica (iniciat al segle X), però totalment refet després de la conquesta, és el castell-palau de l´Almudaina, que s´alça a un dels costats de la Seu, davant la façana principal, al carrer Palau Reial. De fet, aquesta edificació, més l´arc de la Drassana abans esmentat i l´Hort del Rei de què parlarem a continuació, formaven un conjunt: la residència dels walis (governants) musulmans, convertida després de 1229 en palau reial dels monarques mallorquins i catalanoaragonesos. La reconstrucció data de la primera dècada del segle XIV, i fou dirigida pels mestres d´obra Ponç Descoll i Pere Salvà. És de planta rectangular, tancada per murs de gran altura,  flanquejats per torres de planta quadrada, amb alguns llenços de paret de tàpia pertanyents a l´època musulmana. Hi destaca la torre de l´homenatge, anomenada torre de l´Àngel perquè al seu cim hi ha la figura de l´arcàngel sant Gabriel, obra també de primeries del segle XIV. Les façanes consten de tres plantes. La sud presenta arcs de mig punt a la primera planta, ogivals a la segona i finestres geminades a la tercera. La façana de ponent és més llarga i amb obertures variades. A l´angle nord-oest, vora la costa de la Seu, hi havia la torre dels Caps, anomenada així perquè s´hi exposaven els caps dels executats, que fou enderrocada i substituïda per la torre actual, a principi del segle XX, i és una còpia de la del Castellet de Perpinyà.

A l´interior destaca la capella de Santa Aina, feta durant la reconstrucció, molt semblant a la de Santa Creu de Perpinyà, i que presenta un portal romànic de tradició arcaïtzant, amb arquivoltes llises de mig punt sobre capitells esculpits amb escenes d´animals fantàstics, fet amb marbre pirinenc, i un bell timpà esculpit, obra de Pere de Guines. La planta és rectangular, amb volta de creueria. La peça més valuosa que conté és el retaule de Santa Pràxedis, Sant Jordi i Sant Vidal, obra de Rafel Mòger, de la segona meitat del segle XV. Una altra capella és la de Santa Pràxedis, que conté una imatge de la titular,  esculpida per Huguet Barxa el 1458, on es conserva una relíquia d´aquesta santa. Entre les sales cal remarcar, a l´ala de migjorn, la del Tinell, feta amb grans arcs diafragmàtics apuntats, amb coberta de dos aiguavessos, i que és idèntica a la del castell dels Reis de Mallorca, de Perpinyà. El 1578 l´estructura d´aquesta sala fou modificada, superposant-se a la fàbrica gòtica un pis intermedi, sostingut per voltes de creueria.

Aquest castell es completa amb L´hort del Rei, a l´avinguda d´Antoni Maura. Com indica el seu nom, es tractava del jardí reial  (hort i jardí són conceptes assimilables a l´Edat Mitjana). A final del segle XIX fou urbanitzat, fins que durant la dècada de 1960 s´enderrocaren els edificis que s´hi havien construït i es recuperà l´espai ajardinat actual.

Ja de l´època cristiana, l´edifici religiós més important és sens dubte la catedral, anomenada La Seu, al carrer del Palau Reial. Santiago Rusiñol la definí com «la Catedral més besada pels ponents, i més roent de foc del cel, i més colrada per les centúries». Es tracta d´un edifici situat sobre l´antiga ciutat romana, visible des de tota la badia, l´origen del qual es remunta a la immediata postconquesta, quan l´antiga mesquita que hi havia allà es convertí en temple cristià. La seva construcció arranca a partir del segle XIV, amb l´absis que forma l´actual presbiteri, rere del qual s´eleva la capella de la Trinitat, on hi ha les tombes de dos dels tres reis de la Corona de Mallorca, Jaume II (1276-1311) i Jaume III (1324-1349), obra de Frederic Marès el 1946; cal destacar que les rajoles del paviment són les originals, del segle XIV. L´obra fou dirigida per Ponç Descoll. A mitjan segle XIV, es projectà l´edifici amb les característiques actuals: molta alçada (109,5 metres), llum i lleugeresa. La continuació de l´obra va esser dirigida per Jaume Mates. A final de segle, començà la construcció del portal del Mirador, tasca inicial de Pere Morey, i en el qual més tard intervingué Guillem Sagrera, l´autor de La Llonja. L´altre portal gòtic, a la plaça de l´Almoina, és obra del seu fill Francesc Sagrera (final del segle XV), mentre que el Portal Major i la façana principal o de l´Almudaina foren començats al segle XVI, si bé la façana actual és del segle XIX, després que se´n desplomàs el frontis el 1851. El portal de la plaça de l´Almoina fa angle amb la torre del campanar, també gòtica, amb finestres ogivals i que probablement fou construïda sobre la base del minaret de la mesquita musulmana. I adossada s´hi troba la casa de l´Almoina, anomenada així perquè allà es repartien les almoines als pobres després de la sortida de missa. Es tracta d´una construcció de reduïdes dimensions, amb un portal d´ingrés ogival i adovellat i amb arcs conopials a la primera planta, a més d´elements ja de transició al renaixement. És, a més, una de les millors i més rares mostres del gòtic civil mallorquí.