Cells in diverse organisms can store the information of previous environmental conditions for long periods of time. This form of cellular memory adjusts the cells responses to future challenges, providing fitness advantages in fluctuating environments. Many biological functions, including cellular memory, are mediated by specific recurring patterns of interactions among proteins and genes, known as network motifs. In this review, we focus on three well-characterized network motifs - negative feedback loops, positive feedback loops, and feedforward loops, which underlie different types of cellular memories. We describe the latest studies identifying these motifs in various molecular processes and discuss how the topologies and dynamics of these motifs can enable memory encoding and storage.