An incremental high-cycle fatigue damage model is combined with topology optimization to design structures subject to non-proportional loads. The optimization aims to minimize the mass under compliance and fatigue constraints. The fatigue model is based on the concept of an evolving endurance surface and a system of ordinary differential equations that model the local fatigue damage evolution. A recent model extension that uses a quadratic polynomial endurance function to enhance the accuracy and extrapolation capabilities, especially for non-proportional loads, is used. To enable computationally efficient design updates, an adjoint sensitivity analysis that is consistent with the state solution, requiring only a few linear solves involving the stiffness matrix is derived. Furthermore, a new compliance constraint is developed for uncorrelated, stochastic force components to take worst-case force combinations into account. Numerical examples in both 2D and 3D demonstrate that the proposed framework is able to design structures subject to non-proportional loads.