The main idea of the present work is to extend Eringen's theory of nonlocal elasticity to generalized thermoelasticity with dual-phase-lag and voids. Then we study the propagation of time harmonic plane waves in an infinite nonlocal dual-phase-lag thermoelastic medium with voids. Three sets of coupled dilatational waves and an independent transverse wave may travel with distinct speeds through the medium. All these waves are found to be dispersive in nature. The coupled dilatational waves are damping, while the transverse wave is undamped in a certain range of the angular frequency. Coupled dilatational waves are found to be influenced by the presence of voids, thermal field and elastic nonlocal parameter, while the transverse wave is found to be influenced by the nonlocal parameter, but independent of void and thermal parameters. For a particular model, the effects of angular frequency, elastic nonlocality parameter, and some voids and thermal parameters on the wave speeds and damping coefficients of all the propagating waves have been studied numerically. Some comparisons are made between the results obtained for local and nonlocal cases. All the computed results have been depicted graphically and explained in details.