It is shown that, by utilizing spin-selective quantum interference, the spin polarization of nanostructures deposited on a magnetic substrate with a surface state can be strongly modulated locally and energetically by an appropriate structural design. This finding is deduced from state-of-the-art ab initio calculations and interpreted within an analytical model. We present results for hexagonal Cu corrals and mesoscopic triangular Co islands on Co-covered Cu(111). These systems are experimentally feasible, and the effect should be detectable with current technology.