We revisit the observed frequencies of carbon-enhanced metal-poor (CEMP) stars as a function of the metallicity in the Galaxy, using data from the literature with available high-resolution spectroscopy. Our analysis excludes stars exhibiting clear overabundances of neutron-capture elements and takes into account the expected depletion of surface carbon abundance that occurs due to CN processing on the upper red giant branch. This allows for the recovery of the initial carbon abundance of these stars, and thus for an accurate assessment of the frequencies of carbon-enhanced stars. The correction procedure we develop is based on stellar-evolution models and depends on the surface gravity, log g, of a given star. Our analysis indicates that for stars with Fe/H < or =, slant -2.0, 20% exhibit C/Fe > or =, slanted +0.7. This fraction increases to 43% for Fe/H < or =, slant -3.0 and 81% for Fe/H < or =, slant -4.0, which is higher than have been previously inferred without taking the carbon abundance correction into account. These CEMP star frequencies provide important inputs for Galactic and stellar chemical evolution models, as they constrain the evolution of carbon at early times and the possible formation channels for the CEMP-no stars. We also have developed a public online tool with which carbon corrections using our procedure can be easily obtained.