Electrochemical studies of thiol-capped CdTe nanocrystals in aqueous solution have demonstrated several distinct oxidation and reduction peaks in the voltammograms, with the peak positions being dependent on the size of the nanocrystals. While the size dependence of the reduction and one of the oxidation potentials can be attributed to altering the energetic band positions owing to the quantum size effect, an extraordinary behavior was found for the oxidation peak observed at less positive potentials. In contrast to a prediction based on the quantum size effect, this peak moves to more negative potentials as the nanocrystals' size decreases. Moreover, the contribution of the charge associated with this peak compared to the total charge passed during the nanocrystal oxidation correlates well with the photoluminescence (PL) efficiency of individual fractions of the CdTe nanocrystals. These experimental observations allow a peak to be assigned to the oxidation of Te-related surface traps. The intra-band-gap energy level assigned to these Te-related trap states shifts toward the top of the valence band as the nanocrystal size increases, thus allowing the higher photostability of the larger nanocrystals to be explained. At a certain nanocrystal size, the trap level can even move out of the band gap.