Conditional detection is an important tool to extract weak signals from a noisy background and is closely linked to heralding, which is an essential component of protocols for long distance quantum communication and distributed quantum information processing in quantum networks. Here we demonstrate the conditional detection of time-bin qubits after storage in and retrieval from a photon-echo based waveguide quantum memory. Each qubit is encoded into one member of a photon-pair produced via spontaneous parametric down conversion, and the conditioning is achieved by the detection of the other member of the pair. Performing projection measurements with the stored and retrieved photons onto different bases we obtain an average storage fidelity of 0.885 pm 0.020, which exceeds the relevant classical bounds and shows the suitability of our integrated light-matter interface for future applications of quantum information processing.