In this Letter we report an experiment that verifies an atomic-ensemble quantum memory via a measurement-device-independent scheme. A single photon generated via Rydberg blockade in one atomic ensemble is stored in another atomic ensemble via electromagnetically induced transparency. After storage for a long duration, this photon is retrieved and interfered with a second photon to perform a joint Bell-state measurement (BSM). The quantum state for each photon is chosen based on a quantum random number generator, respectively, in each run. By evaluating correlations between the random states and BSM results, we certify that our memory is genuinely entanglement preserving.