We explore star formation histories (SFHs) of galaxies based on the evolution of the star formation rate stellar mass relation (SFR-M_*_). Using data from the FourStar Galaxy Evolution Survey (ZFOURGE) in combination with far-IR imaging from the Spitzer and Herschel observatories we measure the SFR-M_*_ relation at 0.5<z<4. Similar to recent works we find that the average infrared spectral energy distributions of galaxies are roughly consistent with a single infrared template across a broad range of redshifts and stellar masses, with evidence for only weak deviations. We find that the SFR-M_*_ relation is not consistent with a single power law of the form SFR{propto}M_{star}_^{alpha}^ at any redshift; it has a power law slope of {alpha}~1 at low masses, and becomes shallower above a turnover mass (M_0_) that ranges from 10^9.5^ to 10^10.8^M_{sun}_, with evidence that M_0_ increases with redshift. We compare our measurements to results from state-of-the-art cosmological simulations, and find general agreement in the slope of the SFR-M_*_ relation albeit with systematic offsets. We use the evolving SFR-M_*_ sequence to generate SFHs, finding that typical SFRs of individual galaxies rise at early times and decline after reaching a peak. This peak occurs earlier for more massive galaxies. We integrate these SFHs to generate mass growth histories and compare to the implied mass growth from the evolution of the stellar mass function (SMF). We find that these two estimates are in broad qualitative agreement, but that there is room for improvement at a more detailed level. At early times the SFHs suggest mass growth rates that are as much as 10x higher than inferred from the SMF. However, at later times the SFHs under-predict the inferred evolution, as is expected in the case of additional growth due to mergers.