This paper presents a fast direct solver for the Combined Field Integral Equation using higher-order discretizations. By adopting higher-order polynomials with the Method of Moments, the number of unknowns is significantly reduced. The fast direct solver leverages the efficiency of the Multi Level Fast Multipole Method by combining it with randomized linear algebra to construct low-rank approximations in a H2 format. The proposed method is fully error controllable and achieves a setup time with computational complexity of O(r3 log N). Numerical results for the scattering problem of a sphere demonstrate high accuracy, and the efficiency is demonstrated on the NASA Almond.