Sejaka abad ke-15, bandar ini telah berada dibawah pemerintahan empayar Brunei.[1][2][3] Namun, Sultan Omar Ali Saifuddin II telah menyerahkan pulau ini kepada pihak Inggeris untuk ditadbir.[1][4][5] Rodney Mundy, seorang laksamana Inggeris, kemudian telah melawat pulau ini dan memberi nama bandar ini sebagai Victoria sempenan menghormati Ratu Victoria[1][6][7][8][9]. Namun ketika penjajahan Jepun di Borneo bermula tanggal 3 Januari 1942 sehingga Jun 1945, pihak Jepun telah mendudukinya dan menjadi sebahagian dari markas ketenteraan Borneo Utara oleh Tentera Tentera 37 Jepun.[1][10] During the Pertempuran Labuan telah dibebaskan oleh Divisi ke-9 Angkatan Tentera Australia Kedua pada 10 Jun 1945 dan diletakkan dibawah Pemerintahan Ketenteraan Inggeris (Borneo) sehingga 15 Julai 1946, apabila ia telah dimasukkan kedalam Koloni Mahkota Borneo Utara.[1] Ketika waktu ini, kerajaan koloni mahkota telah dibentuk semula dan kebanyakan dari infrastruktur yang musnah di bandar Victoria telah dibangunkan kembali.[11][12] Pulau Labuan kemudiannya menjadi sebahagian dari kawasan di negeri Sabah dan pada tahun 1963, Sabah sendiri telah bersama dengan Singapura, Sarawak dan Semenanjung Tanah Melayu membentuk Persekutuan Malaysia. Namun, pada 1984, pulau Labuan telah diserahkan kepada Kerajaan Persekutuan Malaysia untuk digolongkan dalam Wilayah Persekutuan bersama dengan Kuala Lumpur dan Putrajaya.[1] Ia telah dideklarasikan sebagai pusat kewangan luar pesisir bertaraf antarabangsa dan kawasan zon bebas berdagang pada tahun 1990 untuk membantu pertumbuhan pesat Bandar Victoria.[1][13]