Carbon atoms are always present in Fe-based materials, either as impurities even in high purity samples or as an intrinsic constituent in steels. Density Functional Theory calculations have been performed to study the interaction between C atoms and vacancies (V) in α-Fe. We find that the formation of VCn complexes is energetically favourable for n ≤ 3, with VC2 being the most stable one. The energy gain corresponding to the clustering reaction VCn-1 + C → VCn depends mainly on the strength of C-C covalent bonds. The vacancy diffusivity is shown to be significantly modified by the formation of vacancy-carbon complexes, exhibiting non-Arrhenius behaviour. Effective vacancy diffusion coefficients in α-Fe are calculated as a function of temperature and carbon content using a simplified thermodynamic model. The results are discussed in detail in the limiting case of excess of C with respect to vacancies.