The mosaic decorates Room 36 which lies directly on the longitudinal axis of the south portico of the palace. It is the culminating point of the geometric mosaic floor of the portico itself. The room is almost square (6 x 5.50m.). Its rear wall forms a spacious apse once revetted with marble slabs. The decoration of the pavement is especially well suited to the shape of the room. The two front corners, in the shape of triangles, are filled with a floral ornament: yellow-white lilies bend down to the ground, and are contrasted against the dark claret background. The flowers are rendered with a remarkable freshness in a highly pictorial though not naturalistic way. The remaining part of the floor forms a circle in the centre of which there is a medallion (2.20m. in diameter) containing a representation of the mythical duel between Theseus and the Minotaur in the Labyrinth on Crete.
Theseus, an Athenian hero, was the son of the god of the sea, Poseidon, or of king Aegeus of Athens and the Troezen princess Aethra. As a youth, already famous for his deeds, Theseus decided to accompany to Crete the Athenian hostages who were sent to Knossos every seven years as prey for the Minotaur, the cruel half man, half bull living in the depths of the Labyrinth. This painful tribute had been forced upon the Athenians by the Cretan king Minos. The youth decided to fight the monster. Upon arriving in Crete he was helped by Ariadne, daughter of king Minos, who fell in love with the handsome prince. She told Theseus how to enter the Labyrinth and gave him a ball of thread so that he could mark the difficult way back through the corridors of the maze. Theseus killed the Minotaur, thereby freeing the hostages, and sailed away from Crete together with Ariadne.
The scene on the mosaic shows a decisive moment in the fight. Unlike most of the other mosaics with this subject known from various parts of the Roman Empire, the Paphos representation does not limit itself to the main protagonists, i.e. Theseus and the Minotaur alone. In the centre, within a dark cave, there stands the young hero holding a club in his right hand. With the left he grasps the horn of the monster who has already fallen to his knees. An old man, god of the Labyrinth, is seated on the ground; he looks on at the combat, a horrified look on his face. From above the rocks overhanging the cave, Ariadne and another woman, a personification of Crete with a turretted crown upon her head, greet the victorious hero. Besides the cave, which can be understood as the depths of the Labyrinth, the Cretan maze is represented on the mosaic in yet another way in the form of the magnificent frame around the figural scene. This frame is made up of two fairly simple geometric ornaments: a chain of dark claret and light blue diamonds and a multicolored guilloche. Rows of diamonds form a series of ever smaller circles which, however, are not closed. Each of them is divided into segments as if to leave a sinuous path in between. Through these complicated passages runs a guilloche — Ariadne’s thread — showing the way out of the dwelling of the Minotaur. It leads from around the central medallion to the threshold of the room.
Archaeological evidence indicates that the pavement was created at the very end of the 3rd or in the early 4th century A.D. However, the figural scene had suffered damage, possibly during one of the earthquakes of the 4th century A.D., and had to be restored sometime later, probably in the last quarter of that century. Only stylistic differences (if one disregards the evidence of the mortar bedding) testify to these repairs executed by expert craftsmen, representing great artistic skill. The heads and upper parts of the bodies of Theseus and Crete were remade. The upper part of the medallion between Ariadne and Crete was also altered, a plain white background substituting, most probably, the heads of the Athenian hostages who could have been represented there observing the combat from behind some rocks. The god of the Labyrinth and Ariadne, who belong to the first period, are still close to an early stylistic tradition going back to Hellenistic times. The heads of Theseus and Crete, on the other hand, reveal the style of the approaching Byzantine era. They recall the faces of Christian saints represented on mosaics and paintings in early churches.
The composition of the Theseus mosaic is of particular interest. Unlike other mosaics with this subject, the hero is shown here in the very centre of the picture. The hieratic arrangement of the scene produces the strange impression that the figures have been frozen in their attitudes. The whole scene, in spite of the drama inherent in the depicted episode, is deprived of the pathos and expression found in earlier representations. Theseus appears unconcerned with the outcome of the fight: his large eyes stare into space. We are now in Late Antiquity and the old myth seems to have changed its original meaning. It is no longer the duel itself that is important but the abstract triumph of the hero, who personifies transcendental virtues, over the evil represented by the Minotaur. The allegorical meaning of such a scene is clear, particularly when one considers it within the context of an official residence of the governor who represented the emperor, himself a sublime personification of all virtues. The stylistic qualities of the figures of both the first and the second period and the unusual iconographic richness set this mosaic apart as an exceptional creation. It also gives credit to the ability and the inventiveness of the artists active in Paphos at the time.