This paper focuses on the trajectory design for missions destined to explore Mars and/or Phobos departing from Low Earth Orbit (LEO) and arriving into a Mars-Phobos Distant Retrograde Orbit (DRO). Lunar DROs are also briefly explored as an alternative departure location. A Mars-Phobos DRO is a relatively stable environment which would make both the surfaces of Mars and Phobos available for a reasonable propellant expenditure. This paper presents the methodology used to compute LEO to Mars-Phobos DRO trajectories and results regarding required C3 at launch, v∞ at arrival, Time-of-Flight (TOF), and total ΔV for various Mars-Phobos DROs using full ephemeris planetary data. The results show that propellant-optimal trajectories from LEO to a specified Mars-Phobos DRO could be used as a staging location between Mars and Phobos. Assuming that refueling is available at the targeted DRO, LEO to Low Mars Orbits (LMO) trajectories would have higher total ΔV due to the additional stop at the Mars-Phobos DRO. However, the aforementioned trajectories would have lower Initial Mass in LEO (IMLEO) and thus a lower gear ratio thanks to the added “pit stop” located at the given DRO. This results in a lower overall spacecraft dry mass that needs to be launched into space from Earth’s surface.