Multi-task prioritized controllers are able to generate complex robot behaviors that concurrently satisfy several tasks and constraints. To perform, they often require a human expert to define the evolution of the task priorities in time. In a previous paper [1] we proposed a framework to automatically learn the task priorities using a stochastic optimization algorithm (CMA-ES), maximizing the robot performance for a certain behavior. Here, we learn the task priorities that maximize the robot performance, ensuring that the optimized priorities lead to safe behaviors that never violate any of the robot and problem constraints. We compare three constrained variants of CMA-ES on several benchmarks, among which two are new robotics benchmarks of our design using the KUKA LWR. We retain (1+1)-CMA-ES with covariance constrained adaptation [2] as the best candidate to solve our problems, and we show its effectiveness on two whole-body experiments with the iCub humanoid robot.