A series of five new catalysts I–V based upon the immobilization of 2-deoxyribose-5-phosphate aldolase (DERA) on multiwalled carbon nanotubes (MWCNTs) were prepared, and their use for the formation of the C–C bond via cross-aldol condensation, under environmental friendly conditions, was studied. Among the various employed procedures, the direct immobilization of the enzyme through ionic exchange interactions on oxidized multiwalled carbon nanotubes (ox-MWCNTs) afforded the most efficient catalyst I. This catalyst was shown to be stable with a high tolerance to acetaldehyde, and it maintained its activity for several days, being reused for five runs. The versatility of catalyst I in cross-aldol condensation was evaluated in the reaction of acetaldehyde alone (self-condensation) or in the presence of chloro-acetaldehyde. The corresponding cyclic lactols were obtained in higher yield than native DERA.