The effects of an electron-phonon (e-ph) interaction on the thermoelectric properties of NaxCoO2 are analyzed. By means of dynamical mean-field theory calculations we find that the e-ph coupling acts in a cooperative way with the disorder, enhancing the effective binary disorder potential strength on the Co sites, which stems from the presence or absence of a neighboring Na atom. Hence, the inclusion of the e-ph coupling allows us to assume smaller values of the binary disorder potential strength—which for NaxCoO2 are in fact also more reasonable. More generally, we can conclude that the interplay between disorder effects and coupling to the lattice can be exploited to engineer more efficient thermoelectric materials.