Carbon pre-deposition onto the bare Si(001) surface has been shown to alter the (2 x 1) surface structure by formation of c(4 x 4) reconstructed domains containing a high C-concentration. Here we studied by ultra-high vacuum scanning tunneling microscopy the effect of this restructured surface on the initial stages of Ge nucleation by molecular beam epitaxy. Ge is found to form three-dimensional (3D) islands already at sub-munolayer coverage, resulting in a Volmer-Weber growth mode. Strain effects repel Ge adatoms from the C-rich domains, leading to enhanced Ge island formation on the C-free surface regions in between the c(4 x 4) areas. At a low growth temperature of 350 degreesC, very small three-dimensional islands (3-5 nm in diameter, bright 3-4 ML) with a density of nearly 1 x 10(12) cm - are obtained for only 0.5 ML of Ce. At higher substrate temperatures of approximately 500 degreesC this three-dimensional growth mode is less pronounced, but still evident. The initially nucleated three-dimensional islands define the positions of the larger quantum dots at higher Gr coverage, that exhibit enhanced photoluminescence (PL) properties.