Victoria, ametliku nimega Victoria I, ehitati 2004. aastal Soomes, Rauma laevatehases ja oli Tallinki teine täiesti uus laev. Kaks aastat varem oli sealsamas valminud Victoria õde Romantika, mis praegu seilab Riia–Stockholmi liinil. Victoria on saanud nime Rootsi kroonprintsessi järgi ja laeva ristiema on Eesti päritolu Rootsi kunstnik Ilon Wikland.

Tallinkile üle anti Victoria 9. märtsil 2004 ja Tallinna saabus ta esmakordselt 19. märtsil. Esimese reisi Tallinnast Stockholmi tegi Victoria kaks päeva hiljem, 21. märtsil ja Stockholmi liinil on Victoria seilanud kõik oma 15 aastat. Tema nii-öelda paariliseks on liinil olnud kolm laeva – 2004–2006 Regina Baltica, 2006–2009 ja 2014–2016 Romantika ning 2009–2014 ja aastast 2016 taas Baltic Queen.

Valmimisel oli Victoria kõige suurem Eesti lipu all seilav reisiparvlaev, sest ta on ka veidi suurem kui Romantika. Selle tiitli loovutas ta 2006. aastal vastvalminud Galaxyle. Pikkust on Victorial 193,8 ja laiust 29 meetrit. Neli Wärtsilä V16-diiselmootorit suudavad kiirendada laeva 22 sõlmeni ehk ligi 40 kilomeetrini tunnis.

Tekke on Victorial kokku kümme, millest reisijate käsutuses on kaks autotekki, kolm tekki kajuteid ning kaks tekki kaupluste, restoranide ja baaridega. Lisaks on laeval ka sauna- ja konverentsikeskus. Reisijaid võtab Victoria pardale kuni 2500, neist lõviosa ehk enam kui 2200 tarbeks on olemas ka kajutikohad.

Victoria karjäär on olnud õnnelik ja ainus märkimisvärne intsident leidis aset 4. detsembril 2015 tugeva tormi ajal teel Tallinnast Stockholmi, kui laine lõi lahti vööriradari antenni, mis omakorda purustas kaks kuuendal tekil asuva konverentsikeskuse akent. Kuna neid merel veekindlalt sulgeda ei õnnestunud, oli Victoria sunnitud Tallinna tagasi pöörduma. Tänavuse dokkimise käigus sai antenn laeva vööris asendatud uue lahendusega.

Seekordne uuenduskuur hõlmas muu hulgas kaptenisilla navigatsiooniseadmete vahetust, elektri kaldatoite võimaluse lisamist, samuti kuuendal tekil asuva supermarketi, seitsmendal tekil asuva kohviku ja pubi ümberehitust. Dokkimine kestis 4.–18. märtsini, mille järel Victoria on taas Baltic Queeni kõrval Tallinna–Stockholmi liinil.

Delfi reisikulud Naantalisse tasus Tallink Grupp.