Vincent Vega se forma a inicios del mes de octubre de 1996 y, con un estilo claramente pop, comienza a presentarse en vivo en diversos bares y discos del circuito porteño hasta grabar su primer demo dos meses más tarde; material que incluye algunos de los primeros temas de la banda que, junto a otros más, formarían parte luego de su primer álbum.
A partir de la primera grabación surgen shows en la costa atlántica y durante el mes de enero Vincent Vega realiza una gira por las localidades de Pinamar, Valeria del Mar y Villa Gessel. Al regreso, la banda continúa con sus presentaciones que llegan en 1997 a un total de 15 shows en lugares como El Dorado, Ex Tella, Memorabilia y El C.O.D.O. entre otros.

Entre enero y marzo de 1998 Vincent Vega graba su primer album "Paraíso" conteniendo 15 canciones de gran versatilidad y de una marcada distinción personal. La grabación se realiza en el estudio "Symphony" y cuenta con la coproducción, además de Vincent Vega, de Daniel Lozano y Mario Siperman (Los Fabulosos Cadillacs), Daniel Saiz, Diego Vainer (Fantasías Animadas) y Carlos Pulido. Por otro lado participan como músicos invitados: Daniel Lozano, Diego Vainer, Gastón Satragno (El signo), Braulio Aguirre (Los Siete Delfines) y Toto Rotblat (Los Fabulosos Cadillacs).
La grabación se realiza exclusivamente en disco rígido.

Durante 1998, Vincent Vega se presenta en vivo en 9 oportunidades, en lugares como El Dorado, La Cigale, Oliverio Always, Ozono, Hard Rock, Ave Porco, Sociedad Argentina de Escitores, Evenos, etc. y presenta su álbum oficialmente en Ave Porco el 27 de noviembre.
Durante junio del mismo año se realiza la filmación de su primer video correspondiente al primer corte "Noches Carmesí". La misma cuenta con la dirección de Octavio Facello. Filmada en 35 mm. el video narra una pequeña historia que gira alrededor de los protagonistas y un barman invitado y los muestra en una aventura que culmina con la presentación del producto final que resulta ser el "trago oficial" de Vincent Vega.

Con el apoyo de la revista Los Inrockuptibles se distribuyen 500 copias de "Paraíso" a los suscriptores con el número de noviembre. Por otro lado durante 1999, el disco llega a las bateas de las disquerías distribuido por Random.
Durante 1999 Vincent Vega realiza 15 shows en vivo en lugares como Farfala, Ave Porco, El Observatorio, Centro Cultural Ricardo Rojas (Ciclo Molotov), Podestá, La Cigale, Cemento y Deusa y se presenta en la ciudad de La Plata en tres oportunidades, en el Centro Cultural Malvinas, La Fabriquera y en la Radio Futura en la que hace un unplugged con versiones originales de sus temas.

En el mes de septiembre filma el segundo video "Paraíso", siguiente corte del disco y que le da su nombre. Este video es realizado por Begoña López, Víctor Melton, Octavio Facello y María Fernanda Molina en equipo logrando el producto final luego de diversos tratamientos de imagen y posproducción.
El video es presentado en Comodor el 16 de diciembre de ese año, momento a partir del cual la banda comienza a trabajar más focalizadamente en los temas que integrarían luego su segundo álbum "Bon Vivant".

El segundo álbum de Vincent Vega es grabado entre febrero y abril de 2000 en los estudios Hit & Post, coproducido por Vincent Vega y Carlos Pulido. Incluye 11 canciones entre ellas un remix del tema "Popnography" realizado por Diego Vainer y la instrumentación con arreglos de cuerdas y vientos para la canción "Rojos Cabellos" por Claudio Alsuyet.

En julio de 2000 la editorial Seix Barral premia al escritor Gonzalo Gracés por su novela titulada "Los Impacientes" en la que se incluye parte de la letra de una de las canciones del primer CD "Nada en los pies".

En agosto del mismo año se estrena oficialmente la película "Tesoro Mío" del director Sergio Bellotti, en la que aparece la canción "Noches carmesí" incluida en la banda de sonido. A su vez, Sumaia en voz y Aubele en guitarra participan como músicos invitados en el resto de los temas compuestos y grabados por Mario Siperman y Daniel Lozano.

A comienzos de octubre se realiza en Francia la Bienal de Diseño Saint Etienne en la que la diseñadora Carolina Aubele participará, incluyendo en la musicalización de su desfile la canción "Popnography" .

Durante el verano de 2001, Vincent Vega regraba su segundo disco Bon Vivant y renueva la programación y algunas voces. La presentación está programada para septiembre.