Starvation causes a motivational state that facilitates diverse behaviors such as feeding, walking, and search. Starved "Drosophila" can form odor/feeding-time associations but the role of starvation in encoding of "time" is poorly understood. Here we show that the extent of starvation is correlated with the fly's ability to establish odor/feeding-time memories. Prolonged starvation promotes odor/feeding-time associations after just a single cycle of reciprocal training. We also show that starvation is required for acquisition but is dispensable for retrieval of odor/feeding-time memory. Finally, even with extended starvation, a functional circadian oscillator is indispensable for establishing odor/feeding-time memories.