Aeroelastic phenomena are most often either ignored or roughly approximated when uncertainties are considered in the design optimization process of structures subject to aerodynamic loading, affecting the quality of the optimization results. Therefore, a design methodology is proposed that combines reliability-based design optimization and high-fidelity aeroelastic simulations for the analysis and design of aeroelastic structures. To account for uncertainties in design and operating conditions, a first-order reliability method (FORM) is employed to approximate the system reliability. To limit model uncertainties while accounting for the effects of given uncertainties, a high-fidelity nonlinear aeroelastic simulation method is used. The structure is modelled by a finite element method, and the aerodynamic loads are predicted by a finite volume discretization of a nonlinear Euler flow. The usefulness of the employed reliability analysis in both describing the effects of uncertainties on a particular design and as a design tool in the optimization process is illustrated. Though computationally more expensive than a deterministic optimum, due to the necessity of solving additional optimization problems for reliability analysis within each step of the broader design optimization procedure, a reliability-based optimum is shown to be an improved design. Conventional deterministic aeroelastic tailoring, which exploits the aeroelastic nature of the structure to enhance performance, is shown to often produce designs that are sensitive to variations in system or operational parameters.