Separated flows often set aerodynamic limits for an aircraft flight envelope, and many of these flows remain difficult to predict with Computational Fluid Dynamics (CFD). 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 military aircraft. The review entails: a summary of the physics of flow separation that is especially difficult to model accurately; an historical sketch of seven decades of CFD developments to meet many of the challenges of separated flow predictions; three case studies for an assessment of the current CFD capabilities; and future prospects for further improvements in the CFD simulations using direct numerical simulations (DNS). DNS can be utilized as a virtual wind tunnel to understand complex separated flow and the results used in modelling improvements for RANS and LES CFD methods. Several examples of the capabilities of DNS methods to predict separated aeronautical flows are given. However, significant advances are still needed for separated flow simulations to become practical with reliability comparable to those of attached flow simulations. A possible path forward for future work to achieve this goal is included.