There are almost no remains of the so-called “Dark Centuries” (6th-7th centuries) either in Palma or the rest of the island. The remains of the Muslim period (10th-13th centuries) are also scant, although recent excavations have brought to the surface many traces of the island's Islamic past. An example of this may be found in the basement of the Ca la Gran Cristiana building, current head offices of the Museum of Majorca (Portella St., 5), where part of a 12th century Muslim house, reoccupied during Christian times throughout the 13th and 14th centuries, is still preserved. The most important architectural witness is borne by the so-called Banys Àrabs (Can Serra St., 7), of which only the central lounge, intended for hot baths, and a rectangular annex room with a barrel vault have been preserved. Through a horseshoe arch one can access the main lounge. This lounge has a square plan and is divided in two by twelve columns with a horseshoe arch standing parallel to the walls. The central ceiling has a semi-circular dome with lobed skylights, while the other one has a barrel vault. It is possible that the city’s Jewish community used these baths. It was thought they were built at the end of the 10th century or at the beginning of the 11th, however a more recent hypothesis suggests the possibility that they were built at the beginning of the 12th century, after the Pisan-Catalan raid, using materials from buildings damaged during the devastation.

Another example of that period is the arc de l'Almudaina, located in the street of the same name. The arc is part of a gate of the ancient Roman wall and the Islamic castle, although its current shape is the result of subsequent transformations. Therefore, it does not belong to a strictly Roman or Muslim construction, although there are some elements that could be attributed to the Islamic period. Most probably, its essential characteristics originate in a reconstruction of the Roman gate, which was carried out in the 5th century. The constructive technique of the voussoir’s stonework dates from the Islamic period, whereas the corbels supporting the various additions of neighbouring houses are Gothic.

The Drassana Musulmana is another arch, in this case, of purely Islamic origin, located at the current convergence of the Huerto del Rey gardens and the Parque del Mar. It provided direct access to the ocean from the Almudaina Palace wharf, a small private jetty for Muslim rulers in Majorca, since the medina wharf, in today’s Potopí, was rather far from the city. It is a semi-circular, slightly elliptical arch, with a 59-ft light width. It dates almost certainly from the first Muslim period, the Cordovan caliphate period (10th century), and reflects the Islamic-Majorcan naval power of that time. After being hidden for centuries, the arch was discovered and restored in 1961, when the Cavalry headquarters were demolished due to works carried out Almudaina.
Castell-palau de l’Almudaina, which stands beside Seu, in front of the main facade, on Palau Reial St, also has its origins in the Islamic period (started in the 10th century), although it was completely rebuilt after the conquest. In fact, this building, the aforementioned Drassana arch, and the Hort del Rei referred to below make up the residence of Muslim walis (rulers), which became the royal palace of the Majorcan and Catalan-Aragonese monarchy after 1229. The restoration, by master builders Ponç Descoll and Pere Salvá, dates back to the first decade of the 14th century. It has a rectangular ground plan, closed in by high walls with square towers on its sides, and parts of a wall from the Muslim period. Especially noteworthy is the tribute tower, another work of the early 14th century, called the Tower of the Angel after the image of Archangel St. Gabriel on its top. The facades have three levels. The south facade has a semi-circular arcade on the first floor, an ogival arcade on the second floor, and double windows on the third. The west facade is longer and has various openings. The tower of Caps, so called because the heads of executed prisoners were displayed there, stood in the north-west end, near the ascent to the Seu. The tower was demolished at the beginning of the 20th century and replaced by the present tower, which is a copy of the one found at Castellet de Perpiñán. Inside is the chapel of St. Aina, built during the restoration and very similar to the chapel of St. Creu de Perpiñan. The chapel has a Romanesque facade of archaic tradition, with semi-circular plain archivolts supported by capitals with scenes of fantastic animals sculpted in Pyrenean marble and a beautiful tympanum sculpted by Pere de Guines. It has a square plan and a cross rib vault. Its most valuable piece is the St. Praxedes, St. George and St. Vidal retable painted by Rafel Móger in the second half of the 15th century. St. Praxedes is another chapel, where an image sculpted by Huguet Barxa in 1458 and holding a relic of its patron saint is kept. Of all the rooms, it is worth noting the room of Tinell, located in the south wing, which boasts great diaphragm pointed arches and a double-slope roof and which is identical to the one in the castle of Reis de Mallorca in Perpignan. The structure of this room was modified in 1578 by placing an intermediate storey supported by cross rib vaults on top of the Gothic stonework.

Hort del Rei, located in Antoni Maura avenue, complements this castle. As its name, King's Orchard, indicates, these were the royal gardens (orchard and garden were equal concepts in the Middle Ages). Development began at the end of the 19th century, until all buildings that had been built there were demolished in the 1960s and the current gardened area was recovered.

Since Christian times, the most prominent religious building is, without a doubt, La Seu, the Cathedral, located in Palau Reial Street. Santiago Rusiñol defined it as “the Cathedral most kissed by sunsets, most burned by the sky’s fire, and most weather-beaten by the centuries”. The building is located over an ancient Roman city, it can be seen from all over the bay, and its origins date back to the period immediately following the post-conquest, when the ancient mosque that stood there became a Christian temple. Its construction started in the 14th century with the apse, now part of the presbytery, behind which rises the chapel of Trinitat. Here we find the graves of the three kings of the Majorcan crown, James II (1276-1311), Sancho (1311-1324) and James III (1324-1349), made by Frederic Marés in 1946. It is worth noting that the floor tiles are the original 14th century tiles. The work was directed by Ponç Descoll, and later continued by Jaume Matas. By the mid-14th century, the building was designed with the current characteristics: great height (359,3 ft), light and lightness. By the end of the century, the construction of the Mirador portal began, started by Pere Morey and finished by Guillem Sagrera, who designed La Llonja. His son, Francesc Sagrera, designed the other Gothic portal, located in Almoina square, (end of the 15th century). The Portal Major and the main facade of Almudaina were started in the 16th century, although the present facade dates from the 19th century, after the original facade collapsed in 1851. The Almoina square portal forms an angle with the bell tower, which is also Gothic and has ogival windows, thought to be built on the basis of the Muslim mosque’s minaret. Attached to it we find the casa de l'Almoina, named after the place where alms were given to the poor after Mass. It is a small building, with an ogival gate, voussoirs and an arcade on the first floor, as well as elements belonging to the period of transition to Renaissance. Moreover, it is one of the best and rarest examples of Majorcan Civil Gothic architecture.