The physical properties inferred from the SEDs of z>3 galaxies have been influential in shaping our understanding of early galaxy formation and the role galaxies may play in cosmic reionization. Of particular importance is the stellar mass density at early times which represents the integral of earlier star formation. An important puzzle arising from the measurements so far reported is that the specific star formation rates (sSFR) evolve far less rapidly than expected in most theoretical models. Yet the observations underpinning these results remain very uncertain, owing in part to the possible contamination of rest-optical broadband light from strong nebular emission lines. To quantify the contribution of nebular emission to broad-band fluxes, we investigate the SEDs of 92 spectroscopically-confirmed galaxies in the redshift range 3.8<z<5.0 chosen because the H-alpha line lies within the Spitzer/IRAC 3.6 um filter. We demonstrate that the 3.6 um flux is systematically in excess of that expected from stellar continuum, which we derive by fitting the SED with population synthesis models. No such excess is seen in a control sample at 3.1<z<3.6 in which there is no nebular contamination in the IRAC filters. From the distribution of our 3.6 um flux excesses, we derive an H-alpha equivalent width (EW) distribution. The mean rest-frame H-alpha EW we infer at 3.8<z<5.0 (270 A) indicates that nebular emission contributes at least 30% of the 3.6 um flux. Via our empirically-derived EW distribution we correct the available stellar mass densities and show that the sSFR evolves more rapidly at z>4 than previously thought, supporting up to a 5x increase between z~2 and 7. Such a trend is much closer to theoretical expectations. Given our findings, we discuss the prospects for verifying quantitatively the nebular emission line strengths prior to the launch of the James Webb Space Telescope.