We study a large galaxy sample from the Spitzer Matching Survey of the UltraVISTA ultra-deep Stripes (SMUVS) to search for sources with enhanced 3.6 micron fluxes indicative of strong Halpha emission at z=3.9-4.9. We find that the percentage of Halpha excess sources reaches 37-40% for galaxies with stellar masses log10(M*/Msun) ~ 9-10, and decreases to <20% at log10(M*/Msun) ~ 10.7. At higher stellar masses, however, the trend reverses, although this is likely due to AGN contamination. We derive star formation rates (SFR) and specific SFR (sSFR) from the inferred Halpha equivalent widths (EW) of our Halpha excess galaxies. We show, for the first time, that the Halpha excess galaxies clearly have a bimodal distribution on the SFR-M* plane: they lie on the main sequence of star formation (with log10(sSFR/yr^{-1})<-8.05) or in a starburst cloud (with log10(sSFR/yr^{-1}) >-7.60). The latter contains ~15% of all the objects in our sample and accounts for >50% of the cosmic SFR density at z=3.9-4.9, for which we derive a robust lower limit of 0.066 Msun yr^{-1} Mpc^{-3}. Finally, we identify an unusual >50sigma overdensity of z=3.9-4.9 galaxies within a 0.20 x 0.20 sq. arcmin region. We conclude that the SMUVS unique combination of area and depth at mid-IR wavelengths provides an unprecedented level of statistics and dynamic range which are fundamental to reveal new aspects of galaxy evolution in the young Universe.