Separated flows often set aerodynamic limits for an aircraft flight envelope, and many of these flows remain difficult to predict with Computational Fluid Dynamics. This paper reviews and explores how CFD simulations have been used for predicting separated flows, and the associated aerodynamic performance, throughout the flight envelope, giving special focus to NATO aircraft. The review entails: a summary of the physics of flow separation that is especially difficult to model numerically; an historical sketch of seven decades of CFD developments to meet many of the challenges of separated flow predictions; six case studies for an assessment of the current CFD capabilities; and future prospects for further improvements in the CFD simulations. Significant advances are still needed for separated flow simulations to become practical with reliabilities comparable to attached flow simulations. Some recommendations for future work are included.