Interconnection of behaviors is a process that describes how independently acquired behavioral repertoires can be combined together as a new sequence of behaviors. Manipulations of training, training context and experience of failure in the test situation can hinder this interconnection of previously acquired behaviors. We tested whether wild New Caledonian crows (Corvus moneduloides) could perform a sequence of six independently acquired behaviors in order to fetch a stone from inside a box in a nearby room and use it to gain food from a stone dropping apparatus. However, crows were only trained on three or four of the six behaviors required, and these prerequisites were trained in different contexts. One of the crows that learned four prerequisites solved the task. Neither of the crows that learned three prerequisites solved the task. The crows that learned four prerequisites, but did not solve the problem, were later trained in an additional behavior and then were able to solve the task. These results shows that New Caledonian crows are able to produce novel behavioral solutions to new problems by interconnecting behaviors learned in different contexts, with different consequences and despite experience of failure after the first exposure to the task.