Using landmarks and other scene features to recall locations from new viewpoints is a critical skill in spatial cognition. In an immersive virtual reality task, we asked children 3.5-4.5 years old to remember the location of a target using various cues. On some trials they could use information from their own self-motion. On some trials they could use a view match. In the very hardest kind of trial, they were "teleported" to a new viewpoint and could only use an allocentric spatial representation. This approach provides a strict test for allocentric coding (without either a matching viewpoint or self-motion information) while avoiding additional task demands in previous studies (it does not require them to deal with a small table-top environment or to manage stronger cue conflicts). Both the younger and older groups were able to point back at the target location better than chance when they could use view matching and/or self-motion, but allocentric recall was only seen in the older group (4.0-4.5). In addition, we only obtained evidence for a specific kind of allocentric recall in the older group: they tracked one major axis of the space significantly above chance, r(158) = 0.28, but not the other, r(158) = -0.01. We conclude that there is a major qualitative change in coding for spatial recall around the fourth birthday, potentially followed by further development towards fully flexible recall from new viewpoints.