Victoria Institution pada mula dibina di High Street, Kuala Lumpur, kini jalan Hang Tuah dan dibuka secara rasmi pada 30 Kulai 1894. Nama Victoria Institution mengambil sempena nama Ratu Victoria England bagi memperingati Perayaan Jubli Emas Ratu Victoria. Sekolah ini diasaskan oleh Residen british, saudagar bijuh timah Loke Yew, Kapitan Cina Kuala Lumpur, Yap Kwan Seng dan ahli perniagaan Thanboonsamy Pillay bagi memenuhi keperluan mewujudkan sekolah Inggeris bagi melahirkan kakitangan yang cekap berbahasa Inggeris untuk mengisi jawatan dalam Kerajaan Tempatan. Bangunan ini direkabentuk oleh firma arkitek terkenal, Swan and Maclaren. Pada tahun 1925 satu tapak baru untuk membina sekolah yang lebih besar bagi Victoria Institution telah dikenalpasti oleh kerajaan iaitu di Bukit Petaling. DY.M.M. Sultan Selangor, Sultan Sir Ala'eddin Suleiman Shah telah meletakkan batu asas sekolah Victoria Institution yang baru ini pada 21 September 1927. Bangunan sekolah dengan pelan induk berbentuk 'E' direkabentuk dengan gaya seni bina Art Deco dengan tarikan utamanya adalah menara jam yang mendominasi landskap Bukit Petaling ketika itu. Pada 2 Mac 1929, penuntut Victoria Institution telah berpindah dari High Street ke Bukit Petaling pada 26 Mac 1929, Victoria Institution di Bukit Petaling dirasmikan oleh Sir Hugh Clifford, Pesuruhjaya Tinggi British. Justeru, ia menjadi sekolah menengah pertama di Tanah Melayu. Victoria Institution terletak di No. 71, Jalan Hang Tuah (dahulunya Jalan Shaw), Kuala Lumpur tersohor dengan pasukan kadet yang ditubuhkan pada tahun 1901 oleh guru besarnya yang pertama En. Bennet Eyre Shaw. Beliau juga menubuhkan pasukan pancaragam iaitu Pipe and Bugle Band yang bergabung dengan pasukan kadet. Kini Sekolah Menengah Kebangsaan Victoria mempunyai Pasukan Infranti Kadet. Kumpulan peninjau Pertama Kuala Lumpur dan pasukan pancaragam yang melonjakkan nama sekolah sebagai sekolah yang berprestij dan mengharumkan nama negara setelah menjadi johan pertandingan pancaragam sekolah-sekolah dunia. Dalam arena sejarah tanah air, sekolah inilah majlis penyerahan rasmi tentera Jepun kepada pihak British pada tahun 1945. Selain itu, Persatuan Alumni Victoria Institution dikenali sebagai Victoria Institution Old Boy's Association (VIOBA) telah ditubuhkan pada tahun 1922. Kebanyakkan alumni sekolah ni menjadi tokoh terkenal negara seperti Tan Sri Ananda Krisnan, Alahyarham Mokhtar Dahari, mantan pemain bola sepak negara, Datuk Dr. Mani jegathesan, Datuk Seri Rafidah Aziz, ahli ekonomi dan mantan menteri, Y.B. Dato' Zulhasnan Rafique, Menteri Wilayah Persekutuan, Y.B. Datuk Dr. Ng Yen Yen, Menteri Pembangunan Wanita, Keluarga dan Masyarakat Malaysia dan Y.B. Dato' Seri Hj. Mohd Shafie b. Hj. Apdal, Menteri Perpaduan, Kebudayaan, Kesenian dan Warisan Malaysia.
Jabatan Warisan Negara telah membaikpulih bangunan sekolah ini pada tahun 2009 dan ia menjadi tempat diadakan Majlis Pengisytiharan Warisan Kebangsaan oleh Yang Behormat Menteri Perpaduan, kebudayaan, Kesenian dan Warisan pada tahun yang sama.
