We study the rest-frame ultra-violet sizes of massive (~0.8 x 10^11 M_Sun) galaxies at 3.4<z<4.2, selected from the FourStar Galaxy Evolution Survey (ZFOURGE), by fitting single Sersic profiles to HST/WFC3/F160W images from the Cosmic Assembly Near-Infrared Deep Extragalactic Legacy Survey (CANDELS). Massive quiescent galaxies are very compact, with a median circularized half-light radius r_e = 0.63 +/- 0.18 kpc. Removing 5/16 (31%) sources with signs of AGN activity does not change the result. Star-forming galaxies have r_e = 2.0 +/- 0.60 kpc, 3.2 +/- 1.3 x larger than quiescent galaxies. Quiescent galaxies at z~4 are on average 6.0 +- 0.17 x smaller than at z~0 and 1.9 +/- 0.7 x smaller than at z~2. Star-forming galaxies of the same stellar mass are 2.4 +/- 0.7 x smaller than at z~0. Overall, the size evolution at 0<z<4 is well described by a powerlaw, with r_e = 5.08 +/- 0.28 (1+z)^(-1.44+/-0.08) kpc for quiescent and r_e = 6.02 +/- 0.28 (1+z)^(-0.72+/-0.05) kpc for star-forming galaxies. Compact star-forming galaxies are rare in our sample: we find only 1/14 (7%) with r_e / (M / 10^11 M_Sun)^0.75 < 1.5, whereas 13/16 (81%) of the quiescent galaxies is compact. The number density of compact quiescent galaxies at z~4 is 1.8 +/- 0.8 x 10^-5 Mpc^-3 and increases rapidly, by >5 x, between 2<z<4. The paucity of compact star-forming galaxies at z~4 and their large rest-frame ultra-violet median sizes suggest that the formation phase of compact cores is very short and/or highly dust obscured.