Ge dots are grown on Si(001) substrates pre-covered with 0.05-0.1 monolayers (ML) of carbon. The C pre-deposition reduces the dot size to less than 20 nm at growth temperatures ranging from 450 to 550 ?C. In situ scanning tunnelling microscopy (STM) shows that submonolayer C-deposition locally induces c(4 ? 4) reconstruction. The reconstruction is assigned to clusters of six C atoms localized in the two topmost atomic layers in between two Si surface dimers. The non-uniform distribution of carbon together with the enhanced surface roughness give rise to the early onset of island formation at Ge coverages as low as 2.5 ML. These islands show intense photoluminescence signals at 4 K. STM and transmission electron microscopy show that the islands are irregularly shaped. No faceting is detected up to coverages of 4 ML. At 5.8 ML of Ge islands with (105) side facets and a (001) top facet are observed.