Behavioral flexibility is a critical ability allowing animals to respond to changes in their environment. Previous studies have found evidence of inflexibility when captive chimpanzees are faced with changing task parameters. We provided two groups of sanctuary-housed chimpanzees with a foraging task in which solutions were restricted over time. Initially, juice could be retrieved from within a tube by hand or by using tool materials, but effective solutions were then restricted by narrowing the tube, necessitating the abandonment of previous solutions and adoption of new ones. Chimpanzees responded flexibly, but one group increased their use of effective techniques to a greater extent than the other. Tool-composite techniques emerged in both groups, but primarily in the more flexible group. The more flexible group also showed higher rates of socio-positive behaviors at the task. In conjunction, these findings support the hypothesis that social tolerance may facilitate the emergence and spread of novel behaviors.