Μια νέα σιδηροδρομική γραμμή του μετρό από τη Βικτώρια μέχρι το Walthamstow προτάθηκε για πρώτη φορά από μια ομάδα εργασίας που συστάθηκε από τη ΒρετανικήΕπιτροπή Μεταφορών το 1948. Ο κύριος σκοπός της γραμμής ήταν η αποσυμφόρηση της κεντρικής περιοχής. Το ιδιωτικό νομοσχέδιο που χρειαζόταν για την κατασκευή της εισήχθη στο Κοινοβούλιο το 1955. Το νομοσχέδιο περιέγραφε μια γραμμή από τη Βικτώρια στο Walthamstow (Wood Street). Υπήρχε επίσης μια πρόταση για επέκταση από τη Βικτώρια μέχρι το σταθμό Fulham Broadway στη γραμμή District, αλλά αυτή δεν συμπεριλήφθηκε στο νομοσχέδιο.
Οι εργασίες κατασκευής του τμήματος Walthamstow-Victoria ξεκίνησαν το 1962. Συνεχίστηκαν μέχρι το 1972, όταν άνοιξε ο σταθμός Pimlico. Μια δοκιμαστική σήραγγα από το Tottenham στο Manor House κάτω από την Seven Sisters Road είχε κατασκευαστεί το 1959 και αργότερα ενσωματώθηκε στις σήραγγες λειτουργίας. Ο Πρίγκιπας της Ουαλίας και ο Δούκας του Εδιμβούργου επισκέφθηκαν τη γραμμή κατά τη διάρκεια της κατασκευής της. Τον Ιούλιο του 1968 επισκέφθηκαν τις σήραγγες που κατασκευάζονταν κάτω από το Vauxhall Park.
Στις 4 Αυγούστου 1967, η Υπουργός Μεταφορών Barbara Castle έδωσε την έγκριση για την κατασκευή της επέκτασης του Brixton. Οι προπαρασκευαστικές εργασίες ξεκίνησαν σε μια τοποθεσία στο Bessborough Gardens κοντά στο Vauxhall Bridge Road τον Μάιο του 1967. Στις 28 Ιουνίου 1968, ο Richard Marsh, τότε Υπουργός Μεταφορών, ενέκρινε την πρόταση για την κατασκευή σταθμού στο Pimlico.
Η ονομασία "Victoria line" χρονολογείται από το 1955. Άλλες προτάσεις ήταν η "γραμμή Walvic" (κεντρικός σταθμός Walthamstow-σταθμός Victoria) και η "γραμμή Viking" (σταθμός Victoria-σταθμός King's Cross). Κατά τα στάδια του σχεδιασμού, ήταν γνωστή ως διαδρομή C. Αργότερα, ονομάστηκε γραμμή Βικτώρια από τον David McKenna από τον σταθμό Βικτώρια. Η πρόταση αυτή υποστηρίχθηκε από τον Sir John Elliot.
Η γραμμή Victoria σχεδιάστηκε για να απαλλαγεί από τη συσσώρευση της κυκλοφορίας σε άλλες γραμμές, όπως η γραμμή Piccadilly. Σχεδιάστηκε επίσης για να έχει όσο το δυνατόν περισσότερες διασταυρώσεις, και όλοι οι σταθμοί εκτός από τον Pimlico έχουν διασταύρωση με τουλάχιστον μία άλλη γραμμή του μετρό του Λονδίνου ή των εθνικών σιδηροδρόμων. Προβλεπόταν να κατασκευαστεί η γραμμή μετά το Walthamstow Central μέχρι την Wood Street (Walthamstow), όπου θα ερχόταν επιφανειακά για να τερματίσει δίπλα στο σταθμό των Βρετανικών Σιδηροδρόμων. Ωστόσο, μια καθυστερημένη απόφαση το 1961 είδε τη γραμμή να περικόπτεται μέχρι το σταθμό Walthamstow Central. Μέχρι το 1968 ο σταθμός αυτός ονομαζόταν Walthamstow (Hoe Street).
Κάθε σταθμός της γραμμής Victoria, εκτός από τον Pimlico, κατασκευάστηκε ως σταθμός μετεπιβίβασης και αρκετοί υπάρχοντες σταθμοί αναδιατάχθηκαν ώστε να επιτρέπουν τη διασταυρούμενη μετεπιβίβαση με αυτόν. Σε ορισμένες περιπτώσεις αυτό επιτεύχθηκε με την τοποθέτηση των αποβάθρων της γραμμής Victoria εκατέρωθεν του υφιστάμενου σταθμού. Σε άλλες περιπτώσεις, η γραμμή Victoria χρησιμοποιεί μία από τις παλαιότερες αποβάθρες και η υπάρχουσα γραμμή μεταφέρθηκε σε νέα αποβάθρα.
Στο Euston, τα τρένα της γραμμής Victoria και της Northern (κλάδος Bank) που κατευθύνονται προς βορρά, κινούνται στις διπλανές αποβάθρες, παρόλο που ταξιδεύουν προς αντίθετες κατευθύνσεις. Διασταυρώσεις "ίδιας κατεύθυνσης" μεταξύ των αποβάθρων υπάρχουν στο Stockwell (με τη γραμμή Northern), στο Oxford Circus (με τη γραμμή Bakerloo), στο Highbury & Islington (με τη γραμμή First Capital Connect, αρχικά Northern City Line) και στο Finsbury Park (με τη γραμμή Piccadilly).
Όλοι οι σταθμοί της γραμμής Victoria είχαν αρχικά γαλάζιο χρώμα. Κάθε σταθμός ήταν διακοσμημένος με πλακάκια στις εσοχές των καθισμάτων για να διαφοροποιούνται μεταξύ τους. Κατά τη διάρκεια της κατασκευής της γραμμήςJubilee στα τέλη της δεκαετίας του 1970, τα αρχικά μοτίβα στο σταθμό Green Park αντικαταστάθηκαν από μοτίβα που ταίριαζαν με το νέο σχέδιο για τις πλατφόρμες της γραμμής Jubilee.
Στα τέλη του 2010 και το 2011 εγκαταστάθηκαν σε όλους τους σταθμούς της γραμμής Victoria, εκτός από τον σταθμό Pimlico, αναπηδήσεις πλατφόρμας. Αυτό έγινε για να εξασφαλιστεί η πρόσβαση στα τρένα χωρίς σκαλοπάτια. Οι κανονισμοί για την προσβασιμότητα των σιδηροδρομικών οχημάτων (μη διαλειτουργικό σιδηροδρομικό σύστημα) του 2010 και ο νόμος περί διακρίσεων για άτομα με αναπηρία του 1995 δημιούργησαν την ανάγκη για την εγκατάσταση των αναβαθμών. Οι ανυψώσεις είναι τύπου ράμπας, παρόμοιες με αυτές που εγκαθίστανται σε ορισμένους σταθμούς κύριας γραμμής. Είναι κατασκευασμένα από τοιχοποιία.