We present the evolution of the luminosity-size and stellar mass-size relations of luminous (L_V>3.4x10^10h_70^-2L_sun) and of massive (M_*>3x10^10h_70^-2M_sun) galaxies in the last ~11 Gyr. We use very deep near-infrared images of the Hubble Deep Field-South and the MS1054-03 field in the J_s, H and K_s bands from FIRES to retrieve the sizes in the optical rest-frame for galaxies with z>1. We combine our results with those from GEMS at 0.2<z<1 and SDSS at z~0.1 to achieve a comprehensive picture of the optical rest-frame size evolution from z=0 to z=3. Galaxies are differentiated according to their light concentration using the Sersic index n. For less concentrated objects, the galaxies at a given luminosity were typically ~3+-0.5 (+-2 sigma) times smaller at z~2.5 than those we see today. The stellar mass-size relation has evolved less: the mean size at a given stellar mass was ~2+-0.5 times smaller at z~2.5, evolving proportional to (1+z)^{-0.40+-0.06}. Simple scaling relations between dark matter halos and baryons in a hierarchical cosmogony predict a stronger (although consistent within the error bars) than observed evolution of the stellar mass-size relation. The observed luminosity-size evolution out to z~2.5 matches well recent infall model predictions for Milky-Way type objects. For low-n galaxies, the evolution of the stellar mass-size relation would follow naturally if the individual galaxies grow inside-out. For highly concentrated objects, the situation is as follows: at a given luminosity, these galaxies were ~2.7+-1.1 times smaller at z~2.5 (or put differently, were typically ~2.2+-0.7 mag brighter at a given size than they are today), and at a given stellar mass the size has evolved proportional to (1+z)^{-0.45+-0.10}.