If you had asked me, I would have stated that Picasso was the earliest to do 3D with his cubism (http://en.wikipedia.org/wiki/Cubism) paintings.

Looks like da Vinci was doing it even earlier, but with another technique. According to this recent article (http://news.yahoo.com/s/ap/20100716/ap_on_en_ot/eu_france_da_vinci_1) he used "ultrathin successive layers of paint and glaze, a technique that gave his works their dreamy quality".

Check the article out for the full details.

Andrew