Although in the scientific literature there are studies regarding optimization of structural members subject to static loads or even cyclic in-phase loads, the optimization of structures subject to cyclic, out-of-phase multiaxial loads is still an unexplored issue. In this paper, we present an approach to the problem of size optimization of rectangular cross-section members subject to multiaxial in-phase and out-of-phase cyclic loads. The objective of the optimization is to minimize the cross sectional area of such elements while retaining their fatigue endurance. Under the proposed methodology, optimum values of the area are achieved for six loading cases and for three values of the height to width ratio of the cross section, and these values are reported. The novelty of the approach lies in the inclusion of two multiaxial high cycle fatigue criteria, i.e., Dang Van and Vu-Halm-Nadot ones, as constraints for size optimization problems, fully integrated within an in-house developed tool, capable of handling non-proportional stresses. A plot of the feasible solution space for this optimization problem is also obtained.