Subsurface carbon species of Pd catalysts recently attracted considerable attention because they affect the selectivity of hydrogenation reactions. We calculated the migration of C atoms from the Pd(111) surface to interstitial subsurface sites to be energetically favorable. Yet, thermodynamically more stable is a graphene-like phase on the Pd surface. Applying a density functional method on periodic models, we explored the formation of C(n) (n = 2-4) clusters on Pd(111). At low coverage, carbon monomers on the surface and at octahedral subsurface sites were calculated to be more stable than dimer species, C(2), on the surface. However, at a C coverage of about half a monolayer, the formation of C(2) and C(3) species, precursors of a graphene phase, becomes competitive with migration of C monomers to octahedral subsurface sites. While discussing these findings, we also addressed the problem of C(1) formation on Pd catalysts from simple organics.