Simple organisms manage to thrive in complex environments. Remembering information about the environment is key to take decisions. Physarum polycephalum excels as a giant unicellular eukaryote being even able to solve optimisation problems despite the lack of a nervous system. Here, we follow experimentally the organism's response to a nutrient source and find that memory about nutrient location is encoded in the morphology of the network-shaped organism. Our theoretical predictions in line with our observations unveil the mechanism behind memory encoding and demonstrate the P. polycephalum's ability to read out previously stored information. Our theoretical investigation in the memory formation ability of adaptive networks in general reveals that the erosion of weak network links is key to store information about the past.