Experimental studies have demonstrated that spermatozoa synchronize their flagella when swimming in close proximity. In a Newtonian fluid, it was shown theoretically that such synchronization arises passively due to hydrodynamic forces between the two swimmers if their waveforms exhibit a front–back geometrical asymmetry. Motivated by the fact that most biological fluids possess a polymeric microstructure, here we address synchronization in a viscoelastic fluid analytically. Using a two-dimensional infinite sheet model, we show that the presence of polymeric stresses removes the geometrical asymmetry constraint and therefore even symmetric swimmers synchronize. Such synchronization occurs on asymptotically faster time scales than in a Newtonian fluid, and the swimmers are seen to be driven into a stable in-phase conformation minimizing the energy dissipated in the surrounding fluid.