Background-matching camouflage is a well-established strategy to reduce detection, but implementing this on heterogeneous backgrounds is challenging. For prey with fixed colour patterns, solutions include specialising on a particular visual microhabitat or adopting a compromise or generalist appearance, matching multiple backgrounds imperfectly. Existing studies suggest both approaches can succeed, but most consider relatively simple scenarios, where artificial prey appear against two backgrounds differing in a single visual characteristic. Here, we used computer-based search tasks with human participants to test the relative benefits of specialising and generalising for complex targets, displayed on either two or four types of naturalistic backgrounds. Overall, across two background types, specialisation was beneficial, though its success varied with search duration, such that generalist targets could outperform specialists in the first seconds of each search event. Against four different backgrounds, the initial cost to specialisation was greater, so specialists and generalists ultimately experienced similar survival. Generalists performed better when their patterning was a compromise between backgrounds that were more similar to each other than when backgrounds were more different, with similarity in luminance more relevant than pattern differences. Time-dependence in the relative success of these strategies suggests that predator search behaviour may affect optimal camouflage in real-world situations.