Ce dépôt ferroviaire est construit par la Compagnie des chemins de l'Ouest en 1883, à la limite de Sotteville, entre le pont Mathilde et le pont d'Eauplet. Il est mis en place pour assurer le garage, l'entretien et le ravitaillement des locomotives et comprend pour cela de nombreuses installations : bureaux, vestiaires, atelier de machines-outils, atelier de réparation, forge, remises, rotonde, château d'eau, parc à outils, parc à charbon de 48 000 t et 3 400 m de voies de remisage. Deux grues hydrauliques fabriquées par les usines Chappée du Mans (72) sont mises en service en 1931 pour alimenter en eau les locomotives à vapeur du réseau de l’Ouest.

En 1939, le dépôt regroupe près de 190 locomotives à vapeur destinées en particulier à la traction des trains de marchandises et occupe 1 000 agents pour leur entretien. Durant la Seconde Guerre mondiale, le dépôt de Sotteville constitue une cible privilégiée des bombardements alliés et est quasiment réduit à néant lors de celui d'avril 1944.

La reconstruction complète du dépôt est lancée en 1948. Les remises, dites halles des machines, sont réédifiées avec les mêmes proportions. Au dépôt proprement-dit est adjoint un triage ferroviaire où les wagons sont triés pour former de nouvelles rames. Ce triage comprend à l'origine deux plateaux où les trains sont répartit en fonction de leur provenance, chacun de ces plateaux étant constitué de faisceaux de direction opposée : l'un de Rouen à Paris et l'autre de Paris à Rouen. Les voies de réception des rames à trier sont placées à une extrémité, les voies d'attente au départ des rames reformées après triage sont placées à l'autre extrémité, et entre deux se trouvent les voies de triage proprement dites.

Le triage est entièrement reconstruit au début des années 1960 au moment de l'électrification de la ligne Paris-Le Havre. La nouvelle installation occupe 70 ha en bord de Seine et nécessite d'importants travaux de dragage et d'endiguement du fleuve, d'assèchement et de remblayage du terrain, et la pose de 130 km voies. Après de 18 mois de travaux, le nouveau triage de Sotteville est mis en service le 4 avril 1966. Il comprend : un faisceau de réception (côté Paris) composé de 20 voies de 800 m de longueur utile, un faisceau de triage composé de 40 voies de 900 m, un faisceau d'attente au départ de 65 km de voies, les trois étant reliés par des voies de raccordement. L'ensemble est coordonné par quatre postes de commande : deux postes à relai souple placés à chaque extrémité commandent la circulation sur les voies principales, au milieu un poste à billes contrôle le triage proprement dit, et un quatrième poste assure la formation et le classement des trains jugés bons pour le départ.

Avec une capacité de triage de 4000 trains par jour et un effectif de 600 personnes, il s'impose d'emblée comme l’une des plus grandes gares de triage d’Europe.