The presence of polyiodide complexes have been reported several times when carbon-based materials were doped by iodine molecules, but their formation mechanism remains unclear. By using first-principles calculations that include nonlocal correlation effects by means of a van der Waals density functional approach, we propose that the formation of triiodide (I3(-)) and pentaiodide (I5(-)) is due to a large density of iodine molecules (I2) in interaction with a carbonaceous substrate. As soon as the concentration of surface iodine reaches a threshold value of 12.5% for a graphene monolayer and 6.25% for a bilayer, these complexes spontaneously appear. The corresponding structural and energetic aspects, electronic structures and vibrational frequencies support this statement. An upshift of the Dirac point from the Fermi level with values of 0.45 and 0.52 eV is observed for adsorbed complexes on graphene and intercalated complexes between two layers, respectively. For doped-graphene, it corresponds to a graphene hole density of around 1.1 × 10(13) cm(-2), in quantitative agreement with experiments. Additionally, we have studied the thermal stability at room temperature of these adsorbed ions on graphene by means of ab initio molecular dynamics, which also shows successful p-doping with polyiodide complexes.