We report the likely identification of a substantial population of massive M~10^11M_Sun galaxies at z~4 with suppressed star formation rates (SFRs), selected on rest-frame optical to near-IR colors from the FourStar Galaxy Evolution Survey. The observed spectral energy distributions show pronounced breaks, sampled by a set of near-IR medium-bandwidth filters, resulting in tightly constrained photometric redshifts. Fitting stellar population models suggests large Balmer/4000AA breaks, relatively old stellar populations, large stellar masses and low SFRs, with a median specific SFR of 2.9+/-1.8 x 10^-11/yr. Ultradeep Herschel/PACS 100micron, 160micron and Spitzer/MIPS 24micron data reveal no dust-obscured SFR activity for 15/19 (79%) galaxies. Two far-IR detected galaxies are obscured QSOs. Stacking the far-IR undetected galaxies yields no detection, consistent with the SED fit, indicating independently that the average specific SFR is at least 10x smaller than of typical star-forming galaxies at z~4. Assuming all far-IR undetected galaxies are indeed quiescent, the volume density is 1.8+/-0.7 x 10^-5Mpc^-3 to a limit of log10M/M_Sun>10.6, which is 10x and 80x lower than at z = 2 and z = 0.1. They comprise a remarkably high fraction (~35%) of z~4 massive galaxies, suggesting that suppression of star formation was efficient even at very high redshift. Given the average stellar age of 0.8Gyr and stellar mass of 0.8x10^11M_Sun, the galaxies likely started forming stars before z =5, with SFRs well in excess of 100M_Sun/yr, far exceeding that of similarly abundant UV-bright galaxies at z>4. This suggests that most of the star-formation in the progenitors of quiescent z~4 galaxies was obscured by dust. ; Comment: 8 pages, 4 figures, 1 table, accepted by ApjL