Large-brained diurnal mammals with complex social systems are known to plan where and how to reach a resource, as shown by a systematic movement pattern analysis. We examined for the first time large-scale movement patterns of a solitary-ranging and small-brained mammal, the mouse lemur (Microcebus murinus), by using the change-point test and a heuristic random travel model to get insight into foraging strategies and potential route-planning abilities. Mouse lemurs are small nocturnal primates inhabiting the seasonal dry deciduous forest in Madagascar. During the lean season with limited food availability, these lemurs rely on few stationary food resources. We radio-tracked seven lemurs and analysed their foraging patterns. First change-points coincided with out-of-sight keystone food resources. Travel paths were more efficient in detecting these resources than a heuristic random travel model within limits of estimated detection distance. Findings suggest that even nocturnal, solitary-ranging mammals with small brains plan their route to an out-of-sight target. Thus, similar ecological pressures may lead to comparable spatial cognitive skills irrespective of the degree of sociality or relative brain size.