X-ray free-electron lasers (FELs) are powerful photon sources offering a wide wavelength range, subfemtosecond pulse duration, and high brightness. Most x-ray FELs are based on self-amplified spontaneous emission (SASE). SASE-FEL radiation has excellent transverse but only limited longitudinal coherence, with power and spectral profiles consisting of multiple randomly distributed spikes. In this Letter, we present the first experimental demonstration of mode-locked SASE, which generates periodic trains of phase-locked subfemtosecond pulses, thus providing an x-ray analog of the optical frequency comb. Our approach combines the mode-coupled SASE scheme, where magnetic chicanes between the undulator modules of the FEL increase the coherence of the output radiation, and an external optical laser that restricts the FEL amplification to periodic and short regions of the electron bunch. The work relies on evidence in the frequency and time domains for photons and electrons, respectively, and will benefit investigations of ultrafast dynamics as well as coherent spectroscopy, and enable new types of experiments requiring phase-correlated x-ray pulses.