We present the structural characterization and low-temperature magnetism of the triangular-lattice delafossite NaYbO$_2$. Synchrotron x-ray diffraction and neutron scattering exclude both structural disorder and crystal-electric-field randomness, whereas heat-capacity measurements and muon spectroscopy reveal the absence of magnetic order and persistent spin dynamics down to at least 70,mK. Continuous magnetic excitations with the low-energy spectral weight accumulating at the $K$-point of the Brillouin zone indicate the formation of a novel spin-liquid phase in a triangular antiferromagnet. This phase is gapless and shows a non-trivial evolution of the low-temperature specific heat. Our work demonstrates that NaYbO$_2$ practically gives the most direct experimental access to the spin-liquid physics of triangular antiferromagnets.