Una nuova ferrovia a tubi che va da Victoria a Walthamstow fu proposta per la prima volta da un gruppo di lavoro istituito dalla British Transport Commission nel 1948. Lo scopo principale della linea era quello di decongestionare la zona centrale. Il disegno di legge privato necessario per la sua costruzione fu introdotto in Parlamento nel 1955. Il disegno di legge descriveva una linea da Victoria a Walthamstow (Wood Street). C'era anche una proposta per un prolungamento da Victoria alla stazione di Fulham Broadway sulla linea del Distretto, ma questo non era incluso nel disegno di legge.
I lavori di costruzione della sezione di Walthamstow-Victoria sono iniziati nel 1962. Proseguirono fino al 1972, quando fu aperta la stazione di Pimlico. Nel 1959 era stato costruito un tunnel di prova da Tottenham a Manor House sotto Seven Sisters Road, che fu poi integrato nei tunnel di corsa. Il Principe di Galles e il Duca di Edimburgo visitarono la linea durante la sua costruzione. Nel luglio 1968 visitarono i tunnel che si stavano costruendo sotto Vauxhall Park.
Il 4 agosto 1967 il Ministro deiTrasporti, Barbara Castle, ha approvato la costruzione dell'ampliamento di Brixton. I lavori preparatori iniziarono in un sito sui giardini di Bessborough Gardens vicino a Vauxhall Bridge Road nel maggio 1967. Il 28 giugno 1968, Richard Marsh, allora ministro dei Trasporti, approvò la proposta di costruire una stazione a Pimlico.
Il nome "Linea Victoria" risale al 1955. Altri suggerimenti sono stati "Walvic line" (stazione centrale di Walthamstow - stazione di Victoria) e "Viking line" (stazione di Victoria - stazione di King's Cross). Durante le fasi di pianificazione, era conosciuta come Route C. In seguito, è stata chiamata "Victoria line" dal nome della stazione Victoria da David McKenna. Questo suggerimento fu appoggiato da Sir John Elliot.
La linea Victoria è stata progettata per eliminare gli accumuli di traffico su altre linee, come la linea Piccadilly. E' stata anche progettata per avere il maggior numero di interscambi possibile, e tutte le stazioni, tranne Pimlico, hanno un interscambio con almeno un'altra linea della metropolitana di Londra o della National Rail. Era stato previsto di costruire la linea oltre Walthamstow Central fino a Wood Street (Walthamstow), dove sarebbe arrivata in superficie per terminare accanto alla stazione della British Railways. Tuttavia, una tardiva decisione nel 1961 ha visto la linea tagliare la linea fino alla stazione centrale di Walthamstow. Fino al 1968 questa stazione si chiamava Walthamstow (Hoe Street).
Ogni stazione della linea Victoria, ad eccezione di Pimlico, è stata costruita come stazione di interscambio e diverse stazioni esistenti sono state riorganizzate per consentire l'interscambio multipiattaforma con essa. In alcuni casi ciò è stato ottenuto posizionando le piattaforme della linea Victoria su entrambi i lati della stazione esistente. In altri casi la linea Victoria utilizza una delle piattaforme più vecchie e la linea esistente è stata spostata su una nuova piattaforma.
A Euston, i treni della Northbound Victoria e della Northern line (filiale di Bank) viaggiano lungo i binari uno accanto all'altro, anche se viaggiano in direzioni opposte. Gli interscambi multipiattaforma "verso la stessa direzione" sono disponibili a Stockwell (con la linea Northern), Oxford Circus (con la linea Bakerloo), Highbury & Islington (con la First Capital Connect, in origine la Northern City Line) e a Finsbury Park (con la linea Piccadilly).
Tutte le stazioni della linea Victoria erano originariamente piastrellate di colore azzurro. Ogni stazione era decorata con motivi di piastrelle sulle nicchie dei posti a sedere per differenziarle l'una dall'altra. Durante la costruzione della lineaJubilee alla fine degli anni Settanta, i motivi originali della stazione di Green Park sono stati sostituiti da motivi corrispondenti al nuovo design delle piattaforme della linea Jubilee.
I gobbe della piattaforma sono stati installati su tutte le stazioni della Victoria Line, ad eccezione di Pimlico, alla fine del 2010 e del 2011. Questo è stato fatto per fornire un accesso ai treni senza gradini. Il Rail Vehicle Accessibility (Non Interoperable Rail System) Regulations 2010 e il Disability Discrimination Act 1995 hanno creato la necessità di installare le gobbe. Le gobbe sono del tipo a rampa, simili a quelle installate in alcune stazioni della linea principale. Sono di costruzione in muratura.