Co-evolution of robot morphologies and control systems is a new and interesting approach for robotic design. However, the increased size and ruggedness of the search space becomes a challenge, often leading to early convergence with sub-optimal morphology-controller combinations. Further, mutations in the robot morphologies tend to cause large perturbations in the search, effectively changing the environment, from the controller’s perspective. In this paper, we present a two-stage approach to tackle the early convergence in morphology-controller co-evolution. In the first phase, we allow free evolution of morphologies and controllers simultaneously, while in the second phase we re-evolve the controllers while locking the morphology. The feasibility of the approach is demonstrated in physics simulations, and later verified on three different real-world instances of the robot morphologies. The results demonstrate that by introducing the two-phase approach, the search produces solutions which outperform the single co-evolutionary run by over 10%.