We propose tailoring exchange interactions in magnetic monolayer films by tuning the adjacent nonmagnetic substrate. As an example, we demonstrate a ferromagnetic-antiferromagnetic phase transition for one monolayer Fe on a Ta(x)W(1-x)(001) surface as a function of the Ta concentration. At the critical Ta concentration, the nearest-neighbor exchange interaction is small and the magnetic phase space is dramatically broadened. Complex magnetic order such as spin spirals, multiple-Q, or even disordered local moment states can occur, offering the possibility of storing information in terms of ferromagnetic dots in an otherwise zero-magnetization state matrix.