Carbon nanotube mechanical resonators have attracted considerable interest because of their small mass, the high quality of their surface, and the pristine electronic states they host. However, their small dimensions result in fragile vibrational states that are difficult to measure. Here we observe quality factors $Q$ as high as $5times10^6$ in ultra-clean nanotube resonators at a cryostat temperature of 30 mK, where we define $Q$ as the ratio of the resonant frequency over the linewidth. Measuring such high quality factors requires both employing an ultra-low noise method to detect minuscule vibrations rapidly, and carefully reducing the noise of the electrostatic environment. We observe that the measured quality factors fluctuate because of fluctuations of the resonant frequency. The quality factors we measure are record high; they are comparable to the highest $Q$ reported in mechanical resonators of much larger size, a remarkable result considering that reducing the size of resonators is usually concomitant with decreasing quality factors. The combination of ultra-low size and very large $Q$ offers new opportunities for ultra-sensitive detection schemes and quantum optomechanical experiments.