Local constraints play an important role in the effective description of many quantum systems. Their impact on dynamics and entanglement thermalization are just beginning to be unravelled. We develop a large $N$ diagrammatic formalism to exactly evaluate the bipartite entanglement of random pure states in large constrained Hilbert spaces. The resulting entanglement spectra may be classified into `phases depending on their singularities. Our closed solution for the spectra in the simplest class of constraints reveals a non-trivial phase diagram with a Marchenko-Pastur (MP) phase which terminates in a critical point with new singularities. The much studied Rydberg-blockaded/Fibonacci chain lies in the MP phase with a modified Page correction to the entanglement entropy, $Delta S_1 = 0.513595cdots$. Our results predict the entanglement of infinite temperature eigenstates in thermalizing constrained systems and provide a baseline for numerical studies.