Observations suggest that the interstellar medium (ISM) might have been highly enriched in carbon at very early times. We explore nucleosynthesis in massive carbon-enhanced metal-poor (CEMP) stars of 12-$40, mathrm{M}_odot$ formed from such an ISM with [Fe] ≤ -2. We find substantial production of elements heavier than Fe, mostly up to Sr, by the weak s-process in stars with initial abundances of [CNO] > -1.5. Even heavier elements, up to Ba, can be produced for [CNO] > -0.5. The efficiency of this s-process is sensitive to the initial enhancement of C (or more generally, CNO) and mass of the star, with the yield increasing approximately linearly with the initial Fe abundance. The s-process in CEMP stars of ${gtrsim } 20 , mathrm{M}_odot$ with [CNO] > -1.5 can be an important source for heavy elements in the early Galaxy. © 2018 The Author(s) Published by Oxford University Press on behalf of the Royal Astronomical Society.