In the frontier field of nano-magnetism understanding complex magnetic structures is crucial. We demonstrate that the spin-polarized scanning tunneling microscope (SP-STM) offers a great potential to unravel complex magnetic superstructures on different length scales. Different operating modes of a SP-STM@footnote 1@ will be discussed: It is shown that the spectroscopy mode (SP-STS) and the modulating tip-magnetization mode (SP-STMTM) are ideal to analyze complex magnetic structures on a mesoscopic length scale as created by atomic-scale ferromagnetism. Further we propose the application of the constant-current mode of a SP-STM for the investigation of surfaces of complex atomic-scale magnetic structures of otherwise chemically equivalent atoms. A recent application@footnote 2@ gave evidence of the capabilities of the SP-STM in terms of the first unambigious proof of two-dimensional antiferromagnetism in magnetic monolayer films on non-magnetic substrates predicted already in 1988.@footnote 3@ We argue, that in general any magnetic superstructure leads to an SP-STM image characteristic of the superstructure and is not superimposed on the image of the chemical lattice. This opens the door to study even more complex magnetic structures such as non-collinear spin-structures or spin-density waves. We present calculated SP-STM images of frustrated antiferromagnets on triangular lattices: a coplanar non-collinear periodic Néel state for Cr/Ag(111) and a multiple spin-density wave state of a Mn-monolayer on Cu(111), which we determined in Ref.@footnote 4@ to be the magnetic ground states of these systems. All calculations are based on the vector-spindensity formulation of the density functional theory. @FootnoteText@ @footnote 1@ D. Wortmann et al., Phys. Rev. Lett. 86, accepted (2001). @footnote 2@ S. Heinze et al., Science 288, 1805 (2000). @footnote 3@ S. Blügel et al., Phys. Rev. Lett. 60, 1077 (1988). @footnote 4@ Ph. Kurz et al., Phys. Rev. Lett. 86, 1106 (2001).