This paper addresses the problem of how to reconfigure a tetrahedral formation in a fuel-optimal manner. The objective of this research is to formulate and solve an optimal control problem that results in a single-orbit, minimum-fuel reconfiguration strategy such that, after reconfiguration, the four spacecraft are in an orbit that creates an acceptable tetrahedral configuration throughout a portion of the orbit. In particular, an acceptable tetrahedron is one that meets specified size and shape requirements. The reconfiguration problem is posed as a multiple-phase nonlinear optimal control problem and is solved via direct transcription using the Gauss pseudospectral method. The results obtained in this study provide insight into the structure of the optimal mission design and demonstrate the generality, computational efficiency, and accuracy of the Gauss pseudospectral method.