The electronic structure of NdTe3 in the charge density wave phase (CDW) is investigated by angle-resolved photoemission spectroscopy. The combination of high-quality crystals and careful surface preparation reveals subtle and previously unobserved details in the Fermi surface topology, allowing an interpretation of the rich and unexplained quantum oscillations in the rare earth tritellurides RTe3. In particular, several closed Fermi surface elements can be observed that are related to CDW-induced replicas of the original bands, leading to the curious situation in which a CDW does not only remove Fermi surface elements but creates new ones that are observable in transport experiments. Moreover, a large residual Fermi surface is found in the CDW gap, very close to the position of the gapped normal-state Fermi surface. Its area agrees very well with high-frequency quantum oscillations in NdTe3 and its presence is explained by either a phase separation between normal state and CDW regions or by strong electron-phonon coupling combined with the quasi one-dimensional character of the CDW. Finally, we identify the origin of the low-frequency α quantum oscillations ubiquitous for the lighter R elements in the RTe3 family and responsible for the high mobility in these compounds.