The 2017 Event Horizon Telescope (EHT) observations of the central source in M87 have led to the first measurement of the size of a black-hole shadow. This observation offers a new and clean gravitational test of the black-hole metric in the strong-field regime. We show analytically that spacetimes that deviate from the Kerr metric but satisfy weak-field tests can lead to large deviations in the predicted black-hole shadows that are inconsistent with even the current EHT measurements. We use numerical calculations of regular, parametric, non-Kerr metrics to identify the common characteristic among these different parametrizations that control the predicted shadow size. We show that the shadow-size measurements place significant constraints on deviation parameters that control the second post-Newtonian and higher orders of each metric and are, therefore, inaccessible to weak-field tests. The new constraints are complementary to those imposed by observations of gravitational waves from stellar-mass sources.