Broken fourfold rotational (C4) symmetry is observed in the experimental properties of several classes of unconventional superconductors. It has been proposed that this symmetry breaking is important for superconducting pairing in these materials, but in the high-Tc cuprates this broken symmetry has never been observed on the Fermi surface. Here we report a pronounced anisotropy in the angle dependence of the interlayer magnetoresistance of the underdoped high transition temperature (high-Tc) superconductor YBa2Cu3O6.58, directly revealing broken C4 symmetry on the Fermi surface. Moreover, we demonstrate that this Fermi surface has C2 symmetry of the type produced by a uniaxial or anisotropic density-wave phase. This establishes the central role of C4 symmetry breaking in the Fermi surface reconstruction of YBa2Cu3O6+δ, and suggests a striking degree of universality among unconventional superconductors. © 2017 The Author(s).