The hierarchical nature of galaxy formation suggests that a supermassive black hole binary could exist in our galactic center. We propose a new approach to constraining the possible orbital configuration of such a binary companion to the galactic center black hole Sagittarius A* (Sgr A*) through the measurement of stellar orbits. Focusing on the star S0-2, we show that requiring its orbital stability in the presence of a companion to Sgr A* yields stringent constraints on the possible configurations of such a companion. Furthermore, we show that precise measurements of time variations in the orbital parameters of S0-2 could yield stronger constraints. Using existing data on S0-2 we derive upper limits on the binary black hole separation as a function of the companion mass. For the case of a circular orbit, we can rule out a 10(5) M companion with a semimajor axis greater than 170 au or 0.8 mpc. This is already more stringent than bounds obtained from studies of the proper motion of Sgr A*. Including other stars orbiting the galactic center should yield stronger constraints that could help uncover the presence of a companion to Sgr A*. We show that a companion can also affect the accretion process, resulting in a variability that may be consistent with the measured infrared flaring timescales and amplitudes. Finally, if such a companion exists, it will emit gravitational wave radiation, potentially detectable with the Laser Interferometer Space Antenna (LISA).