The luminosity-size and mass-size distributions of galaxies out to z~3 are presented. We use very deep near-infrared images of the Hubble Deep Field-South in the Js, H, and Ks bands, taken as part of FIRES at the VLT, to follow the evolution of the optical rest-frame sizes of galaxies. For a total of 168 galaxies with Ks,AB<=23.5, we find that the rest-frame V-band sizes re,V of luminous galaxies (V>~2×1010 h-2 Lsolar) at 2~2×1010 h-2 Msolar has changed by 20% (+/-20%) since z~2.5. Both results can be reconciled by the fact that the stellar M/L ratio is lower in the luminous high-z galaxies than in nearby ones because they have young stellar populations. The lower incidence of large galaxies at z~3 seems to reflect the rarity of galaxies with high stellar mass. Based on observations collected at the European Southern Observatory, Paranal, Chile (ESO LP 164.O-0612), and also on observations with the NASA/ESA Hubble Space Telescope, obtained at the Space Telescope Science Institute, which is operated by AURA, Inc., under NASA contract NAS 5-26555.