In this paper, we develop a novel algorithm for spacecraft trajectory planning in an uncooperative cluttered environment. The Spherical Expansion and Sequential Convex Programming (SE—SCP) algorithm first uses a spherical expansion based sampling algorithm to explore the workspace. Once a path is found from the start position to the goal position, the algorithm generates a locally optimal trajectory within the homotopy class using sequential convex programming. If the number of samples goes to infinity, then the SE—SCP’s trajectory converges to the globally optimal trajectory in the workspace. The SE—SCP algorithm is computationally efficient, therefore it can be used for real-time applications on resource-constrained systems. We also present numerical simulations and comparisons with existing algorithms.