Theoretical investigations have provided proof-of-principle calculations suggesting measurements of stellar or pulsar orbits near the Galactic Center could strongly constrain the properties of the Galactic Center black hole, local matter, and even the theory of gravity itself. As in previous studies, we use a Markov chain Monte Carlo to quantify what properties of the Galactic Center environment measurements can constrain. In this work, however, we also develop an analytic model (Fisher matrix) to understand what parameters are well-constrained and why. Using both tools, we conclude that existing astrometric measurements cannot constrain the spin of the Galactic Center black hole. Extrapolating to the precision and cadence of future experiments, we anticipate that the black hole spin can be measured with the known star S2. Our calculations show that we can measure the dimensionless black hole spin to a precision of ∼0.1 with weekly measurements of the orbit of S2 for 40 years using the GRAVITY telescope’s best resolution at the Galactic Center, i.e., an angular resolution of 10 μarcsec and a radial velocity resolution of 500 m/s. An analytic expression is derived for the measurement uncertainty of the black hole spin using the Fisher matrix in terms of observation strategy, star’s orbital parameters, and instrument resolution. From it we conclude that highly eccentric orbits can provide better constraints on the spin, and that an orbit with a higher eccentricity is more favorable even when the orbital period is longer. We also apply it to S62, S4711, and S4714 to show whether they can constrain the black hole spin sooner than S2. If in addition future measurements include the discovery of a new, tighter stellar orbit, then future data could conceivably enable tests of strong field gravity, by directly measuring the black hole quadrupole moment. Our simulations show that with a stellar orbit similar to that of S2 but at one-fifth the distance to the Galactic Center and GRAVITY’s resolution limits on the Galactic Center, we can start to test the no-hair theorem with 20 years of weekly orbital measurements.