Light propagation in multimode fibers produces random-looking speckle patterns at the output, hiding the full information capacity of the fiber. However, the deterministic nature of the process leads to the presence of input-output wave correlations even within the seemingly random output. Here, we report the phenomenon of random polarization memory effect. We observe that, despite random spatial polarization distributions at the multimode fiber output, local polarization states maintain a high degree of correlation with respect to the input state. This new class of optical memory effect opens up previously unexplored opportunities for imaging and sensing through a multimode fiber.