We study the rest-frame ultraviolet (UV) sizes of massive (~0.8 ´ 1011M☉) galaxies at 3.4 ⩽ z < 4.2, selected from the FourStar Galaxy Evolution Survey, by fitting single Sérsic profiles to Hubble Space Telescope/WFC3/ F160W images from the Cosmic Assembly Near-infrared Deep Extragalactic Legacy Survey. Massive quiescent galaxies are very compact, with a median circularized half-light radius re = 0.63 ± 0.18 kpc. Removing 5 16 (31%) sources with signs of active galactic nucleus activity does not change the result. Star-forming galaxies have re = 2.0 ± 0.60 kpc, 3.2 ± 1.3´larger than quiescent galaxies. Quiescent galaxies at z ~ 4 are on average 6.0 ± 1.7´smaller than at z ~ 0 and 1.9 ± 0.7´smaller than at z ~ 2. Star-forming galaxies of the same stellar mass are 2.4 ± 0.7´smaller than at z ~ 0. Overall, the size evolution at 0 < z < 4 is well described by a power law, with re 5.08 0.28(1 z) = ± + -1.44±0.08 kpc for quiescent galaxies and r 6.02 0.28(1 z) e = ± + -0.72±0.05 kpc for star-forming galaxies. Compact star-forming galaxies are rare in our sample: we find only1 14 (7%) with re (M 10 M ) 1.5 11 0.75 < ☉ , whereas 13 16 (81%) of the quiescent galaxies are compact. The number density of compact quiescent galaxies at z ~ 4 is 1.8 ± 0.8 ´ 10-5 Mpc-3 and increases rapidly, by >5´, between 2 < z < 4. The paucity of compact star-forming galaxies at z ~ 4 and their large rest-frame UV median sizes suggest that the formation phase of compact cores is very short and/or highly dust obscured.