Despite being a long-cherished EU ambition and a crucial key to achieving climate goals, there is still no European High-Speed Rail (HSR) network, with the few completed projects often facing disappointing demand resulting in unprofitability. In order to gain insights to profitable network design, this study develops a new formulation to the “Transport Network Design & Frequency Setting Problem” (TNDFSP), as current literature lacks one that can optimally solve the problem for instances of this size while also accounting for demand elasticity. Our model works with elastic and dynamic HSR demand calculated from optimal fare settings and observed travel mode characteristics from competing alternatives. The optimal solution is largely insensitive to fare changes, and in some measures outperform current state-of-the-art. Our model considers the 111 most populous European cities, along with all their origin-destination (OD) pairs, and finds the most profitable network design within a reasonable solution time frame. The results show HSR can be very profitable in Europe, but only when concentrated around a selected group of the largest cities in the western part of the continent. Despite being profitable and contributing significantly to set Green Deal goals, the viability of our network heavily depends on the willingness of several countries to invest significantly in infrastructure construction.