Searching for space-time variations of the constants of Nature is a promising way to search for new physics beyond general relativity and the standard model motivated by unification theories and models of dark matter and dark energy. We propose a new way to search for a variation of the fine-structure constant using measurements of late-type evolved giant stars from the S star cluster orbiting the supermassive black hole in our Galactic Center. A measurement of the difference between distinct absorption lines (with different sensitivity to the fine structure constant) from a star leads to a direct estimate of a variation of the fine structure constant between the star's location and Earth. Using spectroscopic measurements of five stars, we obtain a constraint on the relative variation of the fine structure constant below 10^{-5}. This is the first time a varying constant of nature is searched for around a black hole and in a high gravitational potential. This analysis shows new ways the monitoring of stars in the Galactic Center can be used to probe fundamental physics.