Probability matching has long been taken as a prime example of irrational behaviour in human decision making; however, its nature and uniqueness in the animal world is still much debated. In this paper we report a set of four preregistered experiments testing adult humans and Guinea baboons on matched probability learning tasks, manipulating task complexity (binary or ternary prediction tasks) and reinforcement procedures (with and without corrective feedback). Our findings suggest that probability matching behaviour within primate species is restricted to humans and the simplest possible binary prediction tasks; utility-maximising is seen in more complex tasks for humans as pattern-search becomes more effortful, and we observe it across the board in baboons, altogether suggesting that it is a cognitively less demanding strategy. These results provide further evidence that neither human nor non-human primates default to probability matching; however, unlike other primates, adult humans probability match when the cost of pattern search is low.