We report studies of novel self-assembled magnetic surface swimmers (magnetic snakes) formed from a dispersion of magnetic microparticles at a liquid-air interface and energized by an alternating magnetic field. We show that under certain conditions the snakes spontaneously break the symmetry of surface flows and turn into self-propelled objects. Parameters of the driving magnetic field tune the propulsion velocity of these snakelike swimmers. We find that the symmetry of the surface flows can also be broken in a controlled fashion by attaching a large bead to a magnetic snake (bead-snake hybrid), transforming it into a self-locomoting entity. The observed phenomena have been successfully described by a phenomenological model based on the amplitude equation for surface waves coupled to a large-scale hydrodynamic mean flow equation.