Fonseca was born in New York City to a family of artists. He was raised in the West Village where his father, Gonzalo Fonseca, a Uruguayan sculptor, kept a stone-working studio. His older brother Bruno Fonseca (1958–1994), was a well known contemporary artist.
Fonseca decided not to pursue a college degree in order to practice his craft. He spent 15 years painting in Europe and South America; among his training, the artist spent five years under the guidance of Augusto Torres prior to debuting in the United States. The artist spent several years in Pietrasanta, Italy, as well as Paris, France, in order to learn more about abstract art. After years of training, Fonseca exhibited in New York for the first time in Charles Cowles's SoHo space in 1993.