Microscale propulsion impacts a diverse array of fields ranging from biology and ecology to health applications, such as infection, fertility, drug delivery, and microsurgery. However, propulsion in such viscous drag-dominated fluid environments is highly constrained, with time-reversal and geometric symmetries ruling out entire classes of propulsion. Here, we report the spontaneous symmetry-breaking propulsion of rotating spherical microparticles within non-Newtonian fluids. While symmetry analysis suggests that propulsion is not possible along the fore-aft directions, we demonstrate the existence of two equal and opposite propulsion states along the sphere's rotation axis. We propose and experimentally corroborate a propulsion mechanism for these spherical microparticles, the simplest microswimmers to date, arising from nonlinear viscoelastic effects in rotating flows similar to the rod-climbing effect. Similar possibilities of spontaneous symmetry-breaking could be used to circumvent other restrictions on propulsion, revising notions of microrobotic design and control, drug delivery, microscale pumping, and locomotion of microorganisms.