  We generalize measurement-device-independent quantum key distribution [ H.-K.
Lo, M. Curty, and B. Qi, Phys. Rev. Lett. 108, 130503 (2012) ] to the scenario
where the Bell-state measurement station contains also heralded quantum
memories. We find analytical formulas, in terms of device imperfections, for
all quantities entering in the secret key rates, i.e., the quantum bit error
rate and the repeater rate. We assume either single-photon sources or weak
coherent pulse sources plus decoy states. We show that it is possible to
significantly outperform the original proposal, even in presence of decoherence
of the quantum memory. Our protocol may represent the first natural step for
implementing a two-segment quantum repeater.
