Né à Detroit en 1969, Vincenzo Natali découvre l'année suivante Toronto, où ses parents s'installent.
Fasciné par la bande dessinée, dont il veut faire son métier, il change son fusil d'épaule à la vision de Star Wars. Quelques années plus tard, à 11 ans, il réalise avec Andre Bilejic (co-scénariste de Cube) un court métrage en Super-8, Dark Empire, puis remet ça trois ans plus tard avec Nuclear Memories. Point commun de ces deux films : la science-fiction et une unhappy-end, marque de fabrique de son réalisateur.
Entré à l'école de cinéma Ryerson Polytechnic Institute, qu'il quitte un an et demi plus tard, Natali devient technicien sur des vidéo-clips, puis storyboarder sur les séries animés "Babar", "Tintin", "Beetlejuice" et "Dog City".
Durant cette période, il réalise deux autres courts métrages (Mouth et Playground), tous deux diffusés dans divers festivals internationaux, puis il travaille comme storyboarder sur des films tels que Boulevard, Blood & Donuts et Johnny Mnemonic.
En 1996, Vincenzo Natali est admis au Canadian Film Center's Resident Program. C'est là qu'il réalise le court métrage Elevated, toujours co-écrit avec Bijelic. C'est avec lui qu'il propose Cube au nouveau département du Film Center, le Feature Film Project. Un projet ambitieux qui séduit les instances. Tourné avec un budget microscopique, le film est présenté à Sundance, puis glane trois récompenses au Festival de Gérardmer (Grand Prix, Prix du public, Prix de la critique).