Exploration (interacting with objects to gain information) and neophobia (avoiding novelty) are considered independent traits shaped by the socio-ecology of a given species. However, in the literature it is often assumed that neophobia inhibits exploration. Here, we investigate how different approaches to novelty (fast or slow) determine the time at which exploration is likely to occur across a number of species. We presented four corvid and five parrot species with a touchscreen discrimination task in which novel stimuli were occasionally interspersed within the familiar training stimuli. We investigated the likelihood that an animal would choose novelty at different stages of its training and found evidence for a shift in the pattern of exploration, depending on neotic style. The findings suggest that faster approaching individuals explored earlier, whilst animals with long initial approach latencies showed similar amounts of exploration but did so later in training. Age rather than species might have influenced the amount of total exploration, with juveniles exploring more than adults. Neotic style varied consistently only for one species and seems to involve a strong individual component, rather than being a purely species-specific trait. This suggests that variation in behavioural phenotypes within a species may be adaptive.