According to the Chronicon Paschale, construction started on the 17th of April in 345. The bathhouse was adorned with statues, among which - according to the Parastaseis Syntomoi Chronikai (85) - statues of Perseus and Andromeda.

Even though the baths were still under construction during Constantius II's (r. 337-361) reign, the orator Themistius already celebrated the emperor's efforts to look for more water sources and that he was building these baths (Oratio IV.58bc).

Multiple authors - Ammianus Marcellinus, Socrates, Nikephoros Callistus, Zonaras - tell a story that the old walls of Chalcedon were used as building materials for the Constantiniae baths. This took place during Valens' reign (r. 364-378), "because the Chalcedonians had sided with the usurper (Procopius, r. 365-366), and had used insulting language towards Valens..." (Socrates, Church History, 4.8). Both Ammianus and Socrates speak of a prophecy written on one of the bricks: water would flow into Constantinople, followed by the arrival of armed warbands. Later sources (12-13th century) such as Nikephoros Callistus and Zonaras give less details. Callistus omits the detail that the walls were torn down because Chalcedon sided with Procopius, and Zonaras even let go of the idea that the bricks were directly used for the bath. Instead, Zonaras believed that they were only used for the aqueduct, and that the water was used for amongst other, bathhouses. Neither Callistus nor Zonaras speak of a prophecy anymore.

According to the Chronicon Paschale (581-82), the baths were now inaugurated as the Theodosianae by the prefect Hierius on 3 October 427. This was during the reign of Theodosius II (r. 402-450), which explains why the baths were named rather after him than Constantius, who started the project 82 years ago.