We discuss a new class of phenomena based on strong interaction between magnetic superstructures and vortices in superconductors. A local variation of the magnetic moment can pin and create vortices spontaneously, changing drastically properties of the superconductor. At the same time, magnetic moments can be changed and strongly interact via coupling with vortices. This highly inhomogeneous mechanism of interaction between superconductivity and magnetism is totally different from the traditional mechanism based on competition of homogeneous order parameters. This mechanism can be realized in a broad class of systems. We discuss the case of superconducting films with magnetic nanoscale dots and recent experiments with rare-earth-nickel-borocarbide magnetic superconductors.