Quantum memory for flying optical qubits is a key enabler for a wide range of applications in quantum information. A critical figure of merit is the overall storage and retrieval efficiency. So far, despite the recent achievements of efficient memories for light pulses, the storage of qubits has suffered from limited efficiency. Here we report on a quantum memory for polarization qubits that combines an average conditional fidelity above 99% and efficiency around 68%, thereby demonstrating a reversible qubit mapping where more information is retrieved than lost. The qubits are encoded with weak coherent states at the single-photon level and the memory is based on electromagnetically-induced transparency in an elongated laser-cooled ensemble of cesium atoms, spatially multiplexed for dual-rail storage. This implementation preserves high optical depth on both rails, without compromise between multiplexing and storage efficiency. Our work provides an efficient node for future tests of quantum network functionalities and advanced photonic circuits.