We present a measurement of the evolution of the stellar mass function (MF) of galaxies and the evolution of the total stellar mass density at 0<z<5. We use deep multicolor data in the Fors Deep Field (FDF; I-selected reaching I_AB=26.8) and the GOODS-S/CDFS region (K-selected reaching K_AB=25.4) to estimate stellar masses based on fits to composite stellar population models for 5557 and 3367 sources, respectively. The MF of objects from the GOODS-S sample is very similar to that of the FDF. Near-IR selected surveys hence detect the more massive objects of the same principal population as do I-selected surveys. We find that the most massive galaxies harbor the oldest stellar populations at all redshifts. At low z, our MF follows the local MF very well, extending the local MF down to 10^8 Msun. The faint end slope is consistent with the local value of alpha~1.1 at least up to z~1.5. Our MF also agrees very well with the MUNICS and K20 results at z<2. The MF seems to evolve in a regular way at least up to z~2 with the normalization decreasing by 50% to z=1 and by 70% to z=2. Objects having M>10^10 Msun which are the likely progenitors of todays L* galaxies are found in much smaller numbers above z=2. However, we note that massive galaxies with M>10^11 Msun are present even to the largest redshift we probe. Beyond z=2 the evolution of the mass function becomes more rapid. We find that the total stellar mass density at z=1 is 50% of the local value. At z=2, 25% of the local mass density is assembled, and at z=3 and z=5 we find that at least 15% and 5% of the mass in stars is in place, respectively. The number density of galaxies with M>10^11 Msun evolves very similarly to the evolution at lower masses. It decreases by 0.4 dex to z=1, by 0.6 dex to z=2, and by 1 dex to z=4.