Exoplanets that reside in systems with a resolved debris disk represent a small fraction of the entire population of known directly imaged exoplanets. Among these, the only known system to also be widely separated from the inner planetary region, external to the host system’s debris disk is HD 106906, a 15 Myr-old short-period (49 d) spectroscopic binary which hosts a wide-separation (737 au) planetary-mass (~11 MJup) companion, HD 106906 b. The system’s debris disk has a pronounced asymmetry that dynamical models have suggested is the result of gravitational perturbation by the planet, but observations have not been able to significantly constrain the companion’s orbital motion to confirm this. Here we present the first detection of orbital motion of HD 106906 b using four epochs of Hubble Space Telescope observations taken over a 14-year baseline. By cross-registering the position of background stars in our images with the Gaia DR2 astrometric catalogue, we are able to improve the uncertainty on previous astrometric measurements as well as introduce a new measurement taken in 2017 which altogether provides a statistically significant (>3σ) detection of a 31.8 ± 7.0 mas eastward motion of the companion on its approximately 15000 yr orbit. We fit a standard seven-parameter Keplerian orbit to our measured astrometry and estimate the mutual inclination between the orbit of the planet and the inner debris disk to be either 36 ± 27/14 deg or 44 ± 27/14 deg depending on the true orientation of the orbit of the planet. We find there is a strong negative correlation between periastron and mutual inclination (orbits with smaller periastra are consistent with a more misaligned orbital configuration). Our estimates of the semi-major axis, eccentricity, inclination, and periastron are comparable to the predicted orbital parameters for the hypothetical Planet Nine in our own solar system, showing that a Planet Nine-like architecture can be established very early in the evolution of a planetary system.