The construction of novel compound tools through assemblage of otherwise non-functional elements involves anticipation of the affordances of the tools to be built. Except for few observations in captive great apes, compound tool construction is unknown outside humans, and tool innovation appears late in human ontogeny. We report that habitually tool-using New Caledonian crows (Corvus moneduloides) can combine objects to construct novel compound tools. We presented 8 naïve crows with combinable elements too short to retrieve food targets. Four crows spontaneously combined elements to make functional tools, and did so conditionally on the position of food. One of them made 3- and 4-piece tools when required. In humans, individual innovation in compound tool construction is often claimed to be evolutionarily and mechanistically related to planning, complex task coordination, executive control, and even language. Our results are not accountable by direct reinforcement learning but corroborate that these crows possess highly flexible abilities that allow them to solve novel problems rapidly. The underlying cognitive processes however remain opaque for now. They probably include the species" typical propensity to use tools, their ability to judge affordances that make some objects usable as tools, and an ability to innovate perhaps through virtual, cognitive simulations.