Two groups of rats, one rewarded with sweetened food and the other rewarded with medial forebrain bundle (MFB) stimulation, were trained to home in on and dig for a buried object coated with a target odor. After each group had 15 training trials, MFB rats searched with greater accuracy and speed than food-rewarded rats. MFB rats were subsequently tested (1) after 6 weeks with no additional practice; (2) with food or non-food distractor odors, and (3) with major spatial alterations to the search environment, and in all cases searched with the same high accuracy, short search time, and low level of distractibility as in baseline. These results suggest that the high motivation provided by MFB reward engenders rapidly formed, long-lasting, and surprisingly flexibly deployable "habit" memories.