We presented a quantum-enhanced atomic clock protocol based on groups of sequentially larger Greenberger-Horne-Zeilinger (GHZ) states, which achieved the best clock stability allowed by quantum theory up to a logarithmic correction. The simultaneous interrogation of the laser phase with such a cascade of GHZ states realized an incoherent version of the phase estimation algorithm that enabled Heisenberg-limited operation while extending the Ramsey interrogation time beyond the laser noise limit. We compared the new protocol with state of the art interrogation schemes, and showed that entanglement allowed a significant quantum gain in the stability for short averaging time.