This study investigated the extent to which 3- and 4-year-old children may rely on associative memory representations to pass an unexpected-contents false-belief task. In Experiment 1, 4-year-olds performed at chance in both a standard Smarties task and a modified version highlighting the secrecy of the contents of the tube. These results were interpreted as evidence that having to infer the answer to a false-belief question (without relying on memory representations) is generally difficult for preschool children. In Experiments 2a, 2b, and 2c, 3-year-olds were tested at 3-month intervals during their first year of preschool and showed better performance in a narrative version of the Smarties task (chance level) than in the standard version (below-chance level). These children performed even better in an associative version of the narrative task (above-chance level) where they could form a memory representation associating the protagonist with the expected contents of a box. The results of a true-belief control suggest that some of these children may have relied on their memory of the protagonist’s preference for the original contents of the box (rather than their understanding of what the protagonist was expecting to find inside). This suggests that when 3-year-olds passed the associative unexpected-contents task, some may have been keeping track of the protagonist’s initial preference and not only (or not necessarily) of the protagonist’s false belief. These results are interpreted in the light of current accounts of Theory of Mind development and failed replications of verbal false-belief tasks.