Long-term memory can be critical to a species' survival in environments with seasonal and even longer-term cycles of resource availability. The present, longitudinal study investigated whether complex tool behaviors used to gain an out-of-reach reward, following a hiatus of about 3 years and 7 months since initial experiences with a tool use task, were retained and subsequently executed more quickly by experienced than by naïve chimpanzees. Ten of the 11 retested chimpanzees displayed impressive long-term procedural memory, creating elongated tools using the same methods employed years previously, either combining 2 tools or extending a single tool. The complex tool behaviors were also transferred to a different task context, showing behavioral flexibility. This represents some of the first evidence for appreciable long-term procedural memory, and improvements in the utility of complex tool manufacture in chimpanzees. Such long-term procedural memory and behavioral flexibility have important implications for the longevity and transmission of behavioral traditions.