When the position of an object oscillates, so does its velocity.

For a harmonic oscillator, the position and velocity, when plotted together, trace out a circle or ellipse.

Where does this ellipse live?

Not in ordinary space! It lives in phase space: a point in phase space says both the position and velocity of an object.