Parrots and corvids show outstanding innovative and flexible behaviour. In particular, kea and New Caledonian crows are often singled out as being exceptionally sophisticated in physical cognition, so that comparing them in this respect is particularly interesting. However, comparing cognitive mechanisms among species requires consideration of non-cognitive behavioural propensities and morphological characteristics evolved from different ancestry and adapted to fit different ecological niches. We used a novel experimental approach based on a Multi-Access-Box (MAB). Food could be extracted by four different techniques, two of them involving tools. Initially all four options were available to the subjects. Once they reached criterion for mastering one option, this task was blocked, until the subjects became proficient in another solution. The exploratory behaviour differed considerably. Only one (of six) kea and one (of five) NCC mastered all four options, including a first report of innovative stick tool use in kea. The crows were more efficient in using the stick tool, the kea the ball tool. The kea were haptically more explorative than the NCC, discovered two or three solutions within the first ten trials (against a mean of 0.75 discoveries by the crows) and switched more quickly to new solutions when the previous one was blocked. Differences in exploration technique, neophobia and object manipulation are likely to explain differential performance across the set of tasks. Our study further underlines the need to use a diversity of tasks when comparing cognitive traits between members of different species. Extension of a similar method to other taxa could help developing a comparative cognition research program.