La basilique primitive d’Arles était probablement située dans un quartier appelé aujourd’hui l’Auture et était dédiée à saint Étienne. Le transfert de la cathédrale à son emplacement actuel longtemps attribué à Hilaire ou à son prédécesseur Patrocle, n’a pu avoir lieu qu’après l’épiscopat de Césaire.En effet cette église primitive disparaît dans la tourmente des invasions du VIIe siècle puis est reconstruite à son emplacement actuel à l’époque carolingienne. Elle est à nouveau reconstruite à la fin du XIe siècle avec la construction d’un chœur et du transept puis de la nef. Le chœur sera reconstruit au XVe siècle avec la création d’un déambulatoire.
Le transept, partie la plus ancienne, est réalisé en appareils grossiers, à joints épais, sans marque de tâcherons. A la croisée du transept s’élève une coupole surmonté d’un robuste clocher roman, haut de 42 m et de section carrée. Cette tour comprend trois étages en retrait les sur les autres et un quatrième étage très court. Les deux premiers étages sont ornés de bandes lombardes, le troisième de pilastres à chapiteaux corinthiens. Ce clocher ressemble à ceux de Moustiers-Sainte-Marie et de Castellane.
La nef centrale est une des plus imposante de la Provence romane avec ses 40 m de long, 15 m de large et 20 m de haut. Elle est divisée en cinq travées. Cette nef se caractérise par des appareils admirables de régularité sur lesquels sont gravées de nombreuses marques de tâcherons. Elle est couverte d’une voûte en berceau brisé dont l’insertion sur les murs latéraux est décorée d’une imposte ornée de feuilles d’acanthe. Cette voûte repose sur des doubleaux à ressaut dont les piédroits sont décorés de colonnettes cannelées ou torses, terminés par des chapiteaux corinthiens. Le chantier de la nef s’effectue durant le second quart du XIIe siècle, époque où plusieurs églises sont édifiées ou réédifiées. Il faut faire abstraction des anciennes hypothèses qui ont voulu identifier à tort les murs d’un édifice antérieur réutilisé dans la nef, la façade et la sacristie à partir d’une interprétation erronée des maçonneries.
La nef est éclairée par des fenêtres hautes ouvertes au dessus des grandes arcades qui la font communiquer avec les bas-côtés.
En 1835 sont découverts sous les deux premières travées de la nef, des vestiges consistant en trois espaces parallèles d’axe est-ouest, voûtés en berceaux, communicant entre eux. Cet ensemble rectangulaire de 15 m de long et 9 m de large a fait l’objet d’interprétations diverses : vestiges de l’église primitive, substruction d’un monument du Bas-Empire. Pour Marc Heijmans la meilleure hypothèse serait celle d’un entrepôt datant de la fin de l’antiquité ou du début du haut moyen âge
De même, des fouilles de 1870 ont mis au jour quelques vestiges d’une crypte dont les rares observations ont été consignées par Revoil. Cette crypte débutait au début de la quatrième travée et se prolongeait jusqu’au carré du transept, voire sous l'abside. Au même niveau que celui de l’ancienne nef (bien plus bas que le niveau actuel) qu’elle prolongeait, elle supportait le chœur et les absides auxquels on accédait par un escalier de 18 marches (environ 4 m). D’après l’historien Jacques Thirion, cette crypte, probablement d’origine carolingienne, aurait été l’élément structurant de la reconstruction générale de la seconde église romane au XIIe siècle. Quoi qu’il en soit, elle fut détruite au milieu du XVe siècle, lors de la reconstruction du chœur gothique dont elle bouchait la perspective.
La décision de reconstruire le chœur roman a peut-être été prise sous l'archiépiscopat de Louis Aleman (1423-1450), mais la réalisation effective des travaux ne se fera qu’après sa mort car les pèlerinages dus aux miracles qui se seraient produits sur sa tombe, nécessitèrent la transformation de l’église. L’abside et le chœur romans sont détruits pour faire place à un très vaste chœur gothique avec déambulatoire pour permettre la circulation des pèlerins et chapelles rayonnantes.
Le chœur gothique commencé en 1454 par le cardinal archevêque Pierre de Foix est terminé en 1464. Il comprend deux travées droites, une abside à cinq pans et un déambulatoire ouvrant sur huit chapelles dont cinq latérales (trois au nord et deux au sud) et trois rayonnantes, ces dernières à cinq pans.
Au XIVe siècle une petite chapelle dédiée à saint André, aujourd’hui chapelle des âmes du purgatoire, est ajoutée au bas-côté nord contre la quatrième travée. De même au XVe siècle une autre chapelle dédiée à saint Pierre, aujourd’hui à saint Antoine de Padoue, est construite contre la troisième travée au nord. En 1620 la chapelle des rois comprenant deux travées couvertes de voûtes d’ogives avec liernes et tiercerons est ajoutée au sud, à hauteur de la quatrième et cinquième travée de la nef.