Strength design is a critical aspect of ensuring the safety and reliability of composite structures in service, as stress concentration will lead to fracture, damage, and fatigue. Multi-scale and multi-material variable stiffness design optimization of fiber-reinforced composites, through concurrent optimization of structural topology and fiber orientation, enhances their potential for lightweight design and stress reduction. Conventional stress-constrained structural topology optimization faces inherent challenges, including stress singularity and local optima, high computational cost from large-scale constraints, difficulty in coordinating local stress constraints with global structural performance, and stress nonlinearity. When stress-related constraints are introduced, multi-scale variable stiffness optimization of composite materials faces additional challenges. These arise from the complex failure modes of anisotropic materials, where a single stress measure cannot adequately represent failure mechanisms; the inherent coupling between macro-scale topology and micro-scale fiber orientation, which demands efficient characterization methods for coordinated optimization; and intrinsic difficulties of variable stiffness design, including susceptibility to local optima when fiber angles serve as design variables, combinatorial explosion of discrete angle combinations, and reduced design space imposed by predefined curve functions. Therefore, this study develops a multi-scale variable stiffness optimization framework for composite structures under stress-related failure constraints. Based on the first-order shear deformation theory, the normal distribution fiber optimization interpolation scheme is employed, and the Tsai–Wu failure criterion is considered as the stress-related constraint. To address the large-scale constraint issue, the p-norm approach is adopted to aggregate the Tsai–Wu failure criterion into a reduced set of stress-related constraints, and a stress penalization method is applied to mitigate stress singularities. Using the adjoint vector method, explicit sensitivities of macro-scale topology and micro-scale fiber angle design variables are derived for both with respect to the compliance minimization and the Tsai–Wu stress-related constraints. Numerical studies on a single-layer L-shaped beam, a multi-layer L-shaped laminated plate, and a single-layer pillow-shaped beam for multi-scale optimization demonstrate the proposed framework. Compar