La costruzione del Victoria Embankment iniziò nel 1865 e fu completata nel 1870 sotto la direzione di Joseph Bazalgette. Faceva parte di un triplice lavoro tendente a realizzare anche Albert Embankment, da Lambeth end del Westminster Bridge a Vauxhall e il Chelsea Embankment da Millbank a Cadogan Pier a Chelsea nei pressi di Battersea Bridge.^[1] Era un progetto del Metropolitan Board of Works. L'impresa che realizzò l'opera era Thomas Brassey.^[2] La spinta iniziale fu dettata dalla necessità di fornire Londra di un moderno sistema fognario. Un'altra considerazione importante fu quella di dare sollievo alla congestione sullo Strand e Fleet Street.

Il progetto prevedeva la costruzione al di fuori della riva del Tamigi, restringendo il letto del fiume. I lavori di costruzione richiedevano l'acquisto e la demolizione di gran parte delle proprietà lungo il fiume con un costo molto elevato. Il tunnel per la District Railway venne costruito all'interno dell'Embankment e coperto per costruirvi sopra la strada. La riva del fiume venne costruita in granito e vennero realizzate delle condotte forzate destinate ad essere aperte con la bassa marea per immettere i liquami diluiti quando le piogge inondavano il sistema. Vennero interrati per dare un supporto al sistema di drenaggio e per rinuovere periodicamente i banchi di fango.^[3]

Al livello stradale, in aggiunta alle nuove arterie, vennero realizzati due giardini pubblici. Uno di questi addossato agli edifici governativi di Whitehall e l'altro che andava da Hungerford Bridge a Waterloo Bridge. I giardini contenevano molte statue, tra cui un monumento a Bazalgette. La sezione dei giardini tra il Ponte di Waterloo e la stazione di Charing Cross comprendeva anche un grande palco dove venivano dati spettacoli musicali e il palazzo sul fiume del 1626 dell'ex York House costruito per il duca di Buckingham.

La sezione di Victoria fu la più complessa delle tre realizzate. Era molto più grande, più complessa e più significativa per la metropoli rispetto alle altre due e venne ufficialmente inaugurata il 13 luglio 1870 dal principe di Galles e dalla principessa Luisa.^[4] Quando la gente si riferisce a "the Embankment" di solito pensa a quello di Victoria. Il costo totale della costruzione fu stimato £ 1.260.000 e l'acquisto di immobili da demolire in £ 450.000. Il costo totale comprende quello dei materiali utilizzati per la costruzione del rilevato.^[3]

La costruzione del Victoria Embankment si rivelò difficile a causa della dimensione dell'opera. Il Parlamento assicurò che il lavoro sarebbe durato tre anni, ma la realtà fu ben diversa. C'era una forza lavoro inadeguata e alcune questioni nella progettazione e difficoltà negli espropri crearono dei ritardi. Vi fu anche la difficoltà di acquisire le autorizzazioni per mantenere l'accesso dei battelli a vapore a Westminster e Hungerford. Inoltre, tempo e denaro vennero persi nella sperimentazione di un nuovo tipo di cofferdam, una struttura utilizzata per mantenere l'acqua fuori dal cantiere, di fondamentale importanza per la costruzione degli argini lungo la riva del Tamigi.^[3]

Nel dicembre 1878 il Victoria Embankment fu la prima strada delle isole britanniche ad essere illuminata con un impianto elettrico.^[5] L'illuminazione venne realizzata con 20 Yablochkov candles alimentate da un generatore elettrico. Il 16 marzo 1879 il sistema venne esteso con altre 40 lampade e il 10 ottobre con ulteriori 55.^[6] In precedenza l'illuminazione era realizzata con lampade a gas, e nel giugno 1884 l'illuminazione a gas venne ripristinata in quanto l'elettricità non era ancora competitiva.^[6]