Laser-cooled and quantum degenerate atoms are being pursued as quantum simulators and form the basis of today's most precise sensors. A key challenge toward these goals is to understand and control coherent interactions between the atoms. We observe long-range exchange interactions mediated by an optical cavity, which manifest as tunable spin-spin interactions on the pseudo spin-1/2 system composed of the millihertz linewidth clock transition in strontium. This leads to one-axis twisting dynamics, the emergence of a many-body energy gap, and gap protection of the optical coherence against certain sources of decoherence. Our observations will aid in the future design of versatile quantum simulators and the next generation of atomic clocks that use quantum correlations for enhanced metrology.