Using observations from the FourStar Galaxy Evolution Survey (ZFOURGE), we obtain the deepest measurements to date of the galaxy stellar mass function at 0.5 < z < 2.5. ZFOURGE provides well-constrained photometric redshifts made possible through deep medium-bandwidth imaging at 1-2um . We combine this with HST imaging from the Cosmic Assembly Near-IR Deep Extragalactic Legacy Survey (CANDELS), allowing for the efficient selection of both blue and red galaxies down to stellar masses ~10^9.5 Msol at z ~ 2.5. The total surveyed area is 316 arcmin^2 distributed over three independent fields. We supplement these data with the wider and shallower NEWFIRM Medium-Band Survey (NMBS) to provide stronger constraints at high masses. Several studies at z<=1 have revealed a steepening of the slope at the low-mass end of the stellar mass function (SMF), leading to an upturn at masses <10^10 Msol that is not well-described by a standard single-Schechter function. We find evidence that this feature extends to at least z ~ 2, and that it can be found in both the star-forming and quiescent populations individually. The characteristic mass (M*) and slope at the lowest masses (alpha) of a double-Schechter function fit to the SMF stay roughly constant at Log(M/Msol) ~ 10.65 and ~-1.5 respectively. The SMF of star-forming galaxies has evolved primarily in normalization, while the change in shape is relatively minor. This is not the case for quiescent galaxies: the depth of our imaging allows us to show for the first time significantly more evolution at Log(M/Msol) < 10.5 than at higher masses. We find that the total mass density (down to 10^9 Msol) in star-forming galaxies has increased by a factor of ~2.2 since z ~ 2.5, whereas in quiescent galaxies it has increased by a factor of ~12 .