Using first-principles calculations, we demonstrate that an Fe monolayer can assume very different magnetic phases on hexagonal hcp (0001) and fcc (111) surfaces of 4d- and 5d-transition metals. Due to the substrates d-band filling, the nearest-neighbor exchange coupling of Fe changes gradually from antiferromagnetic (AFM) for Fe films on Tc, Re, Ru and Os to ferromagnetic on Rh, Ir, Pd, and Pt. In combination with the topological frustration on the triangular lattice of these surfaces the AFM coupling results in a 120-degree Neel structure for Fe on Re and Ru and an unexpected double-row-wise AFM structure on Rh, which is a superposition of a left- and right-rotating 90-degree spin spiral.