The nucleation and growth of Fe on graphene is highly unusual. A constantly increasing island density indicates the presence of strong, predominantly repulsive, adatom interactions. We study these interactions by first-principles calculations to identify their origin. We find that the interactions consist of a short-range attraction and longer-range repulsion. We show that electric dipole-dipole interaction can contribute only part of the repulsive force (∼30%) between Fe adatoms, and the repulsion due to the elastic interaction is small. We suggest that the dominant contribution to the repulsive energy would originate from the indirect (or RKKY) interactions mediated through the delocalized electrons on graphene.