Spatial learning in microorganisms
To build on busukxuan's answer, there are a lot of single-celled organism responses that kind of resemble memory:

Slime mold uses an externalized spatial 'memory' to navigate in complex environments - essentially, a slime mold leaves behind a trail, which it then avoids, allowing it to avoid where it has traveled in the past.

If you apply a periodic stimulus to Physarum, it will anticipate the next stimulus: Popular, openly accessible summary Paywalled journal article.

If the amoeba Dictyostelium sees an increasing cAMP gradient, it will follow that gradient - and then be less sensitive to a reversal in the gradient: Cellular memory in eukaryotic chemotaxis

In fact, even bacteria have some memory - they can figure out whether or not they are going up a chemoattractant gradient by making a comparison with the signal they observed a few seconds ago: Temporal comparisons in bacterial chemotaxis