Optical quantum memory is an essential element for long distance quantum communication and photonic quantum computation protocols. The practical implementation of such protocols requires an efficient quantum memory with long coherence time. Beating the no-cloning limit, for example, requires efficiencies above 50%. An ideal optical fibre loop has a loss of 50% in 100 $mu$ s, and until now no universal quantum memory has beaten this time-efficiency limit. Here, we report results of a gradient echo memory (GEM) experiment in a cold atomic ensemble with a 1/e coherence time up to 1ms and maximum efficiency up to 87$pm$2% for short storage times. Our experimental data demonstrates greater than 50% efficiency for storage times up to 0.6ms. Quantum storage ability is verified beyond the ideal fibre limit using heterodyne tomography of small coherent states.