Olfactory predator search processes differ fundamentally to those based on vision, particularly when odour cues are deposited rather than airborne or emanating from a point source. When searching for visually cryptic prey that may have moved some distance from a deposited odour cue, cue context and spatial variability are the most likely sources of information about prey location available to an olfactory predator. We tested whether the house mouse (Mus domesticus), a model olfactory predator, would use cue context and spatial variability when searching for buried food items; specifically, we tested the effect of varying cue patchiness, odour strength, and cue-prey association on mouse foraging success. Within mouse- and predator-proof enclosures, we created grids of 100 sand-filled Petri dishes and buried peanut pieces in a set number of these patches to represent visually cryptic 'prey'. By adding peanut oil to selected dishes, we varied the spatial distribution of prey odour relative to the distribution of prey patches in each grid, to reflect different levels of cue patchiness (Experiment 1), odour strength (Experiment 2) and cue-prey association (Experiment 3). We measured the overnight foraging success of individual mice (percentage of searched patches containing prey), as well as their foraging activity (percentage of patches searched), and prey survival (percentage of unsearched prey patches). Mouse foraging success was highest where odour cues were patchy rather than uniform (Experiment 1), and where cues were tightly associated with prey location, rather than randomly or uniformly distributed (Experiment 3). However, when cues at prey patches were ten times stronger than a uniformly distributed weak background odour, mice did not improve their foraging success over that experienced when cues were of uniform strength and distribution (Experiment 2). These results suggest that spatial variability and cue context are important means by which olfactory predators can use deposited odour cues to locate visually cryptic prey. They also indicate that chemical crypsis can disrupt these search processes as effectively as background matching in visually based predator-prey systems.