Using the combined capabilities of the large near-infrared Palomar/DEEP-2 survey, and the superb resolution of the Advanced Camera for Surveys HST camera, we explore the size evolution of 831 very massive galaxies (M*>=10^11^h^-2^_70_M_{sun}_) since z~2. We split our sample according to their light concentration using the Sersic index n. At a given stellar mass, both low (n<2.5) and high (n>2.5) concentrated objects were much smaller in the past than their local massive counterparts. This evolution is particularly strong for the highly concentrated (spheroid like) objects. At z~1.5, massive spheroid-like objects were a factor of 4(+/-0.4) smaller (i.e. almost two orders of magnitudes denser) than those we see today. These small sized, high-mass galaxies do not exist in the nearby Universe, suggesting that this population merged with other galaxies over several billion years to form the largest galaxies we see today.