We present 0.5-2 keV, 2-8 keV, 4-8 keV, and 0.5-8 keV cumulative and differential number counts (logN-logS) measurements for the recently completed ~4 Ms Chandra Deep Field-South (CDF-S) survey, the deepest X-ray survey to date. We implement a new Bayesian approach, which allows reliable calculation of number counts down to flux limits that are factors of ~1.9-4.3 times fainter than the previously deepest number-counts investigations. In the soft band, the most sensitive bandpass in our analysis, the ~4 Ms CDF-S reaches a maximum source density of ~27,800 deg-2. By virtue of the exquisite X-ray and multiwavelength data available in the CDF-S, we are able to measure the number counts from a variety of source populations (active galactic nuclei [AGNs], normal galaxies, and Galactic stars) and subpopulations (as a function of redshift, AGN absorption, luminosity, and galaxy morphology), and test models that describe their evolution. We find that AGNs still dominate the X-ray number counts down to the faintest flux levels for all bands and reach a limiting soft-band source density of ~14,900 deg-2, the highest reliable AGN source density measured at any wavelength. We find that the normal-galaxy counts rise rapidly near the flux limits, and at the limiting soft-band flux, reach source densities of ~12,700 deg-2 and make up 46+/-5% of the total number counts. The rapid rise of the galaxy counts toward faint fluxes, and significant normal-galaxy contributions to the overall number counts, indicate that normal galaxies will overtake AGNs just below the ~4 Ms soft-band flux limit and will provide a numerically significant new X-ray source population in future surveys that reach below the ~4 Ms sensitivity limit. We show that a future ~10 Ms CDF-S would allow for a significant increase in X-ray detected sources, with many of the new sources being cosmologically distant (z > 0.6) normal galaxies.