The field of evolutionary robotics shows great promise, but is held back by the lack of results applicable to real world problems or other research fields. The reality gap effects present when moving from virtual to real robots makes evolution based on simulation inefficient for continuous adaption to changing morphology or environments. Evolution on the physical robot does not share these challenges, but each experiment in hardware is limited by the high time requirement of each evaluation. In this paper we suggest using a high level controller with multi-objective optimization of speed and stability to achieve a range of robust gaits for a quadruped robot that does not require excessive tests on the real robot. Using multi-objective evolutionary optimization on the physical robot, we achieved a Pareto front with high performing and robust individuals showing different trade-offs between speed and stability. Single objective optimization of either speed or stability did not yield individuals with a trade-off between the two objective functions. The results show that multi-objective evolutionary optimization on the physical robot is not only feasible, but preferable over using single-objective optimization, given a high level gait controller.