We present a novel high-order shock tracking method, which leverages concepts from implicit shock tracking and extended discontinuous Galerkin (XDG) methods, primarily designed for solving partial differential equations (PDEs) featuring discontinuities. In XDG methods, interfaces (e.g. phases in multi-phase flow) are represented sharply by level set functions, locally enrichening the approximation spaces to incorporate additional jumps. In our work, we develop an XDG method for supersonic flows, accurately representing the shock fronts. At the core of our method lies a constrained optimization problem, where both the XDG coefficients of the solution and of the level set serve as variables. The iterative computation of shock-aligned solutions employs a Sequential Quadratic Programming (SQP) method and is augmented with several measures to ensure robustness. We showcase a proof-of concept for our XDG shock tracking method through a series of two-dimensional problems, including the 1D space-time advection equation, 1D space-time Burgers equation and the steady 2D Euler equations.