La isla fue descubierta el 20 de julio de 1898 por dos capitanes mercantes noruegos, Johannes Nilsen y Ludvig Bernard Sebulonsen. Al día siguiente, el capitán P. W. Nilsen del vapor Victoria, propiedad del aventurero inglés Arnold Pike, avistó la isla y la denominó igual que el barco.
A pesar de que la isla Victoria se encuentra solo a menos de 32 millas náuticas (unos 60 kilómetros) de Kvitøya en el archipiélago Svalbard, se encuentra al este de los territorios sometidos a la soberanía de Noruega de acuerdo con el Tratado de Svalbard en 1920. En consecuencia, la isla era considerada Terra nullius, hasta que un decreto soviético de 15 de abril de 1926 reclamó un sector soviético en la región ártica que también incluía a Tierra de Francisco José y la isla Victoria. Noruega fue notificada el 6 de mayo y protestó oficialmente el 19 de diciembre, oponiéndose a la demanda soviética.
En los años siguientes las autoridades noruegas pusieron mucho esfuerzo en la anexión de la isla Victoria y Tierra de Francisco José. El Ministerio de Asuntos Exteriores no tomó medidas para asentar las afirmaciones oficiales, pero no puso ninguna objeción a la iniciativa privada. En 1929, Lars Christensen, un magnate de la caza de ballenas en cuyas expediciones Noruega se había anexionado la isla Bouvet y la isla de Pedro I en la Antártida, financió una expedición de dos buques, S/S Torsnes and M/C Hvalrossen. A la salida de Tromsø, la tripulación recibió instrucciones detalladas para construir una estación de radio y dejar a un equipo de invernada en Tierra de Francisco José y reclamar la isla Victoria, en nombre de Christensen. La expedición nunca llegó a Tierra de Francisco José ni a la isla Victoria, debido a las condiciones del mar helado. El 29 de julio de 1929, el profesor Schmidt de la Expedición Soviética Sedov izaron la bandera soviética en la bahía Tikaya de la isla Hooker, y declaró que la Tierra de Francisco José formaba parte de la Unión Soviética.
Noruega no protestó oficialmente por la anexión soviética de Tierra de Francisco José, pero continuó sus esfuerzos con respecto a la isla Victoria y un nuevo intento se hizo el año siguiente. El buque M/S Bratvaag llegó a la isla Victoria, el 8 de agosto de 1930. A las 04:30 un grupo de siete hombres saltaron a tierra, entre ellos el líder de la expedición Gunnar Hornos y el capitán del barco Peder Eliassen. Hornos reclamó la isla y levantó un cartel en la playa, indicando la demanda, y dejó materiales de construcción de una cabina, los clavos y un martillo. El verdadero propósito de la expedición Bratvaag se mantuvo en secreto y Noruega no reclamó oficialmente la isla más tarde, probablemente debido al temor de disgustar a la Unión Soviética. En septiembre de 1932, se supo que la Unión Soviética se anexionó la isla.
