In quantum metrology, one of the major applications of quantum technologies, the ultimate precision of estimating an unknown parameter is often stated in terms of the Cram\'er-Rao bound. Yet, the latter is no longer guaranteed to carry an operational meaning in the regime where few measurement samples are obtained, which we illustrate through a simple example. We instead propose to quantify the quality of a metrology protocol by the probability of obtaining an estimate with a given accuracy. This approach, which we refer to as probably approximately correct (PAC) metrology, ensures operational significance in the finite-sample regime. The accuracy guarantees hold for any value of the unknown parameter, unlike the Cram\'er-Rao bound which assumes it is approximately known. We establish a strong connection to multi-hypothesis testing with quantum states, which allows us to derive an analogue of the Cram\'er-Rao bound which contains explicit corrections relevant to the finite-sample regime. We further study the asymptotic behavior of the success probability of the estimation procedure for many copies of the state and apply our framework to the example task of phase estimation with an ensemble of spin-1/2 particles. Overall, our operational approach allows the study of quantum metrology in the finite-sample regime and opens up a plethora of new avenues for research at the interface of quantum information theory and quantum metrology.