The origins of this church date back to the beginning of the IV Century. According to tradition, St Mark brought the message of the Gospel to these lands being sent here by St. Peter. As an Evangelist, during his mission in Aquileia, he met and converted Ermacora who became the first priest of the small Christian community, which slowly grew in number despite the fears and difficulties. He was martyred with his Deacon Fortunato, and they are, together with the Virgin Mary, the patron Saints of the Basilica. 
The frescoes in the crypt, tell their story wrapped in the atmosphere of a legend and some reliquaries hold their mortal remains, which are venerated together with the other martyrs from Aquileia: Ilario and Taziano, Felice and Fortunato, Crisogo, Proto and the Canziani brothers.
The period of persecution ended in the year 313 as a result of the Edict of Costantine and Licio. The Christian community of Aquileia, ruled at that time by Archbishop Theodore, was then finally able to build its first Church, as is stated in an iscription on the mosaic floor. 
The architectural changes, which took place over a period of 1,000 years and which turned the first Theodorian church into the basilica of today, are extremely complex.