Do the orbits of trans-Neptunian objects (TNOs) indicate the existence of a new planet in the outer solar system? Past studies without considering such unknown planets have great difficulties to explain two important properties: 1) TNOs with very high orbital inclinations (i > 45 deg); 2) A large population of TNOs with orbits too distant from Neptune’s gravitational influence (i.e., with perihelia q > 40 au). Here, I performed N-body computer simulations of the outer solar system to investigate the effects of a new planet on the orbital structure beyond Neptune. Considering the currently known orbital structure of TNOs, the formation of TNOs on peculiar orbits, and other constraints, I will discuss preliminary results on the potential orbits and masses of a candidate new planet in the solar system. Based on the gravitational perturbations of such a planet, I will also present observationally testable predictions for new populations of TNOs. Overall, these results will guide future astronomical surveys in the search for undiscovered planets located beyond Neptune.