Understanding the magnetic properties of atomic chains on superconductors is an essential cornerstone on the road towards controlling and constructing topological electronic matter. Yet, even in simple models, the magnetic ground states remain debated. Ferromagnetic (FM), antiferromagnetic (AFM), and spin spiral configurations have been suggested and experimentally detected, while non-coplanar and complex collinear phases have been additionally conjectured. Here, we resolve parts of the controversy by determining the magnetic ground states of chains of magnetic atoms in proximity to a superconductor with Monte-Carlo methods. We confirm the existence of FM, AFM and spin spiral ground states, exclude non-coplanar phases in the model and clarify the parametric region of a $\uparrow\uparrow\downarrow\downarrow$-phase. We further identify a number of novel complex collinear spin configurations, including the periodic spin configurations $\uparrow\uparrow\uparrow\downarrow$, and $\uparrow \uparrow \uparrow \downarrow \uparrow \downarrow \downarrow \downarrow \uparrow \downarrow$, which are in some cases combined with harmonic and anharmonic spirals to form the ground state. We topologically classify the electronic structures, investigate their stability against increasing the superconducting order parameter, and explain the complex collinear order by an effective Heisenberg model with dominant four-spin interactions.