This paper focuses on multi-objective optimization under uncertainty for mechanical design, through a reliability-based formulation referring to the concept of probabilistic nondominance. To address this problem, the implementation of a co-evolutionary strategy is advocated, consisting of the concurrent evolution of two intertwined populations optimized according to coupled subproblems: the upper level optimizer handles the design variables, whereas the corresponding values of the probabilistic thresholds for the objectives (namely the reliable nondominated front) are retrieved at the lower stage. The proposed methodology is successfully applied to six analytical test cases, as well as to the sizing optimization of two truss structures, demonstrating an improved capacity to cover wider ranges of the reliable nondominated front in comparison with all-at-once strategies tackling all types of variables simultaneously.