A novel and eco-friendly three-component reaction of aldehydes, amines, and alkynes (A3 coupling) catalyzed by a recoverable copper(II) carboxymethylcellulose (CMC-Cu^II) catalyst has been developed, producing a diverse range of propargylamines under solvent-free conditions in good yields. The CMC-Cu^II catalyzed reaction is especially effective for reactions involving aromatic and aliphatic aldehydes. High catalytic activity was obtained in the presence of 5 mol% CMC-Cu^II without any other co-catalyst, additives, or bases under aerobic conditions. Moreover, the catalyst can be easily recovered and reused for at least four cycles without significant decrease in its catalytic activity.