Casi no quedan restos de los llamados «Siglos oscuros» (s. VI-IX), ni en Palma, ni en el resto de la isla. También son muy reducidos los de la época musulmana (s. X-XIII), aunque las excavaciones de los últimos años han puesto al descubierto numerosos vestigios del pasado islámico isleño. Una muestra se halla en el subsuelo del edificio de Ca la Gran Cristiana, sede actual del Museu de Mallorca (calle de la Portella, 5), en el que se conserva en parte una casa de origen musulmán, que es del siglo XII, y que se reocupó en época cristiana a lo largo de los siglos XIII y XIV. El testimonio arquitectónico más importante lo constituyen los llamados Banys Àrabs (calle de Can Serra, 7), de los que sólo se ha conservado la sala central, destinada a baños calientes, y una estancia aneja de planta rectangular y con bóveda de cañón. Un arco de herradura da acceso a la sala principal. La planta de esta sala es cuadrada y se halla dividida en dos espacios por doce columnas con arco de herradura, paralelas a las paredes. La cubierta central consta de una cúpula semiesférica con claraboyas lobuladas, mientras que la otra es con bóveda de cañón. Es posible que estos baños los usara la comunidad judía de la ciudad. Tradicionalmente, se ha considerado que se cosntruyeron a finales del siglo X o a principios del siglo XI, pero una hipótesis més reciente plantea la posibilidad que sean de principios del siglo XII, construidos después de la razzia pisanocatalana, aprovechando materiales de edificios afectados por la devastación.

Otra muestra de aquel periodo es el arc de l’Almudaina, situado en la calle de este mismo nombre. Corresponde a una puerta de la antigua muralla romana y de la alcazaba islámica, aunque su estructura actual es fruto de transformaciones posteriores. Por esta razón, no corresponde a una construcción propiamente romana ni tampoco musulmana, aunque hay elementos atribuibles a la época islámica. Lo más probable es que sus rasgos esenciales provengan de una reconstrucción de la puerta romana, hecha durante el siglo V. De la época islámica presenta como técnica constructiva la fábrica conservada sobre las dovelas, mientras que las ménsulas que soportan los distintos añadidos de las casas vecinas son góticas.

Otro arco, en este caso de origen totalmente islámico, es el de la Drassana Musulmana, ubicado en la confluencia actual entre los jardines de el Huerto del Rey y el Parque del Mar. Daba acceso directo desde el mar al muelle del palacio de la Almudaina, un pequeño puerto privado de los gobernantes musulmanes de Mallorca, ya que el puerto de la medina estaba a unos cuantos quilómetros de la ciudad, en el actual Portopí. Es un arco semicircular, ligeramente elíptico, que presenta una anchura de luz de 18 metros. Lo más probable es que sea de la primera época musulmana, durante el período califal cordobés (siglo X), y refleje el poderío naval islamicomallorquín de aquella época. Durante siglos, este arco fue ciego y se descubrió y restauró en 1961, cuando se derribó el cuartel de Caballería, a raíz de las obras de reforma de la Almudaina.

Asimismo proviene de la época islámica (iniciado en el siglo X), pero totalmente rehecho después de la conquista, es el castell-palau de l’Almudaina, que se levanta al lado de la Seu, ante la fachada principal, en al calle Palau Reial. De hecho, esta edificación, más el arco de la Drassana, mencionadao anteriormente y el Hort del Rei del que hablábamos a continuación, formaban un conjunto: la residencia de los walis (gobernantes) musulmanes, convertida después de 1229 en palacio real de los monarcas mallorquines y catalanoaragoneses. La reconstrucción es de la primera década del siglo XIV, y fue dirigida por los maestros de obra Ponç Descoll y Pere Salvá. Es de planta rectangular, cerrada por muros de gran altura, flanqueados por torres de planta cuadrada, con algunos lienzos de paredes de tapia pertenecientes a la época musulmana. Destaca la torre de homenaje, llamda torre del Angel, porque en su cima está la figura del arcángel san Gabriel, obra también de principios del siglo XIV. Las fachadas constan de tres plantas. La sur presenta arcos de medio punto en la primera planta, ogivales en la segunda y ventanas geminadas en la tercera. La fachada de poniente es más larga y con aperturas variadas. En el ángulo noroeste, cerca de la subida de la Seu, había la torre de los Caps, llamada así porque allí se exponían las cabezas de los ejecutados, que fue derribada y subtituída por la torre actual, a principios del siglo XX, y es una copia de la del Castellet de Perpiñán.

En el interior destaca la capilla de Santa Aina, hecha durante la reconstrucción, muy parecida a la de Santa Creu de Perpiñán, y que presenta una portada románica de tradición arcaizante, con arquivoltas lisas de mdio punto sobre capiteles esculpidos con escenas de animales fantásticos, hecho con mármol pirenaico, y un bello tímpano esculpido, obra de Pere de Guines. La planta es rectangular, con bóveda de crucería. La pieza más valiosa que contiene es el retablo de Santa Práxedes, San Jorge y San Vidal, obra de Rafel Móger, de la segunda mitad del siglo XV. Otra capilla es la de Santa Práxedes, que contiene una imagen de la titular, esculpida por Huguet Barxa en 1458, donde se conserva una reliquia de esta santa. Entre las salas hay que señalar, en el ala sur, la del Tinell, hecha con grandes arcos diafragmáticos apuntados, con cubierta de dos vertientes, y que es idéntica a la del castillo9 de los Reis de Mallorca, de Perpiñán. En 1578 la estructura de esta sala se modificó, sobreponiéndose a la fábrica gótica un piso intermedio, sostenido por bóvedas de crucería.

Este castillo se completa con el Hort del Rei, en la avenida de Antoni Maura. Como indica su nombre, se trataba del jardín real (huerto y jardín son conceptos asimilables en la Edad Media). A fines del siglo XIX se urbanizó, hasta que durante la década de 1960 se derribaron los edificios que allí se habían construído y se recuperó el espacio ajardinado actual.

Ya de la época cristiana, el edificio religioso más importante es sin duda alguna la catedral, llamada La Seu, en la calle del Palau Reial. Sabtiago Rusiñol la definió como «la Catedral más besada por los ponientes, y más candente de fuego del cielo, y más curtida por las centurias». Se trata de un edificio situado sobre la antigua ciudad romana, visible desde la totalidad de la bahía, el origen del cual se remonta a la inmediata postconquista, cuando la antigua mezquita que allí había se convirtió en templo cristiano. Su construcción arranca a partir del siglo XIV, con el ábside que forma el actual presbiterio, detrás del cual se eleva la capilla de la Trinitat, donde hay las tumbas de dos de los tres reyes de la Corona de Mallorca, Jaume II II (1276-1311) y Jaume III (1324-1349), obra de Frederic Marés enl 1946; hay que destacar que las baldosas del pavimento son las originales, del siglo XIV. La obra fue dirigida por Ponç Descoll. A mediados del siglo XIV, se preoyectó el edificio con las características actuales: gran altura (109,5 metres), luz y ligereza. La continuación de la obra fue dirigida por Jaume Matas. A fines de siglo, empezó la construcción del portal del Mirador, tarea inicial de Pere Morey, y en el cual más tarde intervino Guillem Sagrera, el autor de La Llonja. El otro portal gótico, en la plaza de la Almoina, es obra de su hijo Francesc Sagrera (fines del siglo XV), mientras que el Portal Major y la fachada principal o de la Almudaina se iniciaron en el siglo XVI, aunque la fachada actual es del siglo XIX, después de desplomarse el frontis en 1851. El portal de la plaza de la Almoina forma un ángulo con la torre del campanario, también gótica, con ventanas ogivales y que probablemente se construyó sobre la base del minarete de la mezquita musulmana. Y allí adosada se halla la casa de l’Almoina, llamada así porque allí se repartían las limosnas a los pobres después de la salida de misa. Se trata de una cosntrucción de reducidas dimensiones, con un portal de ingreso ogival y con dovelas y arcos conopiales en la primera planta, además de elementos ya de transición al renacimiento. Es, además, una de las mejores y más raras muestras del gótico civil mallorquín.