The exploration of interstellar space will require autonomous navigation systems that do not rely on tracking from the Earth. Here I develop a method to determine the 3D position and 3D velocity of a spacecraft in deep space using a star catalogue. As a spacecraft moves away from the Sun, the observed positions and velocities of the stars will change relative to those in a Earth-based catalogue due to parallax and aberration. By measuring just the angular distances between pairs of stars, and comparing these to the catalogue, we can infer the coordinates of the spacecraft via an iterative forward-modelling process. I perform simulations with existing star catalogues to demonstrate the method and to compute its performance. Using the 20 nearest stars and a modest angular distance measurement accuracy of 1", the position and velocity of a spacecraft light years from the Sun moving at relativistic speeds can be determined to within 3 au and 2 km/s respectively. These accuracies improve linearly with the measurement accuracy, e.g. with angles measured to 1 mas the navigation accuracy is 1000 times better. Performance can also be improved using more stars, or by including onboard measurements of the stars' radial velocities, as these too are affected by the spacecraft's position and motion.