Jeden z dwóch okrętów nowego typu, dla którego początkowo przewidziano nazwę „Renown”, został zamówiony w stoczni koncernu Armstrong Whitworth w Elswick. Stępkę położono 23 kwietnia 1885 roku, zaś wodowanie odbyło się 9 kwietnia 1887 roku. Był to pierwszy pancernik zbudowany w stoczni Armstronga. W związku z przypadającym na ten rok złotym jubileuszem królowej Wiktorii, zmieniono na jej cześć nazwę jednostki, chrzcząc ją jako „Victoria”. W trakcie ceremonii wodowania fala, spowodowana przez spływający na wodę kadłub, dotarła aż do nabrzeża, mocząc znajdujących się tam widzów. Prace wykończeniowe na okręcie, podobnie jak na bliźniaczym „Sans Pareil”, przeciągały się w związku z oczekiwaniem na dostawę potężnych dział Armstronga kalibru 413 mm (16,25 cala), dodatkowo w trakcie strzelań próbnych wykryto wady w konstrukcji luf. Ostatecznie „Victoria” weszła do służby w Royal Navy w marcu 1890 roku. Całkowity koszt budowy, łącznie z uzbrojeniem, wyniósł 844 922 ówczesnych funtów szterlingów.