Né à Buffalo de parents siciliens, Vincent Gallo s'intéresse d'abord à la musique. Il quitte l'école à 16 ans et part tenter sa chance à New York. Il joue dans différents groupes et devient l'ami de Jean-Michel Basquiat. Il débute sa carrière d'acteur dans les années 80 avec des spectacles de café-théâtre. Il apparaît pour la première fois au cinéma en 1984 dans un film indépendant, The Way it is d'Eric Mitchell, film dont il compose la musique. Il y joue aux côtés d'un autre acteur débutant, Steve Buscemi.

Il s'essaie ensuite à la réalisation avec deux courts métrages qu'il produit et monte, If You Feel Froggy, Jump et The Gunlover. Il poursuit sa carrière d'acteur entre cinéma indépendant, films d'auteurs et cinéma européen. Il croise le chemin de Claire Denis en 1991 pour le court métrage Keep it for Yourself. Il retrouve la réalisatrice à deux reprises : en 1996 pour Nénette et Boni, dans lequel il tient un second rôle, et en 2001 pour un film choc sur le cannibalisme, Trouble every day.

Fait rare pour un acteur américain, Vincent Gallo tourne régulièrement sous la direction de réalisateurs européens. En 1992, il est un doux rêveur cinéphile dans Arizona Dream d'Emir Kusturica. Un an plus tard, il est le frère perturbé et vindicatif de Winona Ryder dans La Maison aux esprits du Danois Bille August. Acteur au teint diaphane, à l'air éthéré et aux grands yeux clairs, il s'illustre à merveille dans des rôles de personnages instables et fragiles.

Il demeure attaché à ses origines et à ses premières expériences artistiques. En 1996, il incarne Johnny, le jeune frère fougueux de Christopher Walken dans Nos funérailles du New-yorkais Abel Ferrara. En 1998, il écrit et réalise son premier long métrage, Buffalo'66. Ce film, dans lequel il interprète le personnage principal, s'inspire de sa vie à Buffalo. Une fois de plus, il compose la bande originale. En 2003, il écrit, produit et réalise son deuxième long métrage, The Brown Bunny. Il y tient le rôle principal aux côtés d'une actrice emblématique du cinéma indépendant, Chloë Sevigny. Le film est en compétition officielle au festival de Cannes 2003. Cannes qu'il retrouve en 2009 pour la présentation à la Quinzaine des Réalisateurs du film de Francis Ford Coppola, Tetro, dans lequel il incarne le personnage éponyme, un homme qui, après avoir coupé tout lien avec sa famille depuis 10 ans, voit son petit frère, joué par Alden Ehrenreich, venir le chercher à Buenos Aires. C'est en 2010, à la Mostra de Venise, qu'on retrouve cet acteur devenu rare au cinéma. Il y présente son troisième film en tant que réalisateur, Promises Written In Water et reçoit la Coupe Volpi pour son rôle de taliban traqué dans Essential Killing de Jerzy Skolimowski.