According to theory, directional female choice for male sexual ornaments is expected to erode underlying genetic variation. Considerable attention, in this regard, has been given to understanding the ubiquity of heritable genetic variation in both female choice and male sexual traits. One intriguing possibility emerging from this work is that persistent genetic variation could be maintained, over time, by variation in female mate preferences. Here, we report the results of a four-year study showing significant year-to-year fluctuations in mate preferences in a small marine fish, the sand goby, Pomatoschistus minutus. Although the average size of mature fish varied across years, we were unable to find direct evidence linking this variation to differences in female preferences among years. Our results, nevertheless, underscore the importance of temporal fluctuations in female mate preferences, as these can have important consequences for understanding variation in sexual traits and the intensity of sexual selection.