The relationship between the encounter rate of predators with prey and the density of this prey is fundamental to models of predator-prey interactions. The relationship determines, among other variables, the rate at which prey patches are depleted, and hence the impact of predator populations on their prey, and the optimal spatial distribution of foraging effort. Two central assumptions that are made in many models are that encounter rate is directly proportional to prey density and that it is independent of the proportion of prey already removed, other than via the decreased density. We show here, using captive great tits searching for winter moth caterpillars in their natural hiding positions, that neither of these assumptions hold. Encounter rate increased less than directly in proportion to prey density, and it depended not only on the current density of prey, but also on the proportion of prey already removed by previous foragers. Both of these effects are likely to have major consequences for the outcome of predator-prey interactions.