The understanding of metal nucleation on graphene is essential for promising future applications, especially of magnetic metals which can be used in spintronics or computer storage media. A common method to study the grown morphology is to measure the nucleated island density n as a function of growth parameters. Surprisingly, the growth of Fe on graphene is found to be unusual because it does not follow classical nucleation: n is unexpectedtly high, it increases continuously with the deposited amount θ and shows no temperature dependence. These unusual results indicate the presence of long range repulsive interactions. Kinetic Monte Carlo simulations and density functional theory calculations support this conclusion. In addition to answering an outstanding question in epitaxial growth, i.e., to find systems where long range interactions are present, the high density of magnetic islands, tunable with θ, is of interest for nanomagnetism applications.