Bulk-boundary correspondence, a central principle in topological matter relating bulk topological invariants to edge states, breaks down in a generic class of non-Hermitian systems that have so far eluded experimental effort. Here we theoretically predict and experimentally observe non-Hermitian bulk-boundary correspondence, a fundamental generalization of the conventional bulk-boundary correspondence, in discrete-time non-unitary quantum-walk dynamics of single photons. We experimentally demonstrate photon localizations near boundaries even in the absence of topological edge states, thus confirming the non-Hermitian skin effect. Facilitated by our experimental scheme of edge-state reconstruction, we directly measure topological edge states, which match excellently with non-Bloch topological invariants calculated from localized bulk-state wave functions. Our work unequivocally establishes the non-Hermitian bulk-boundary correspondence as a general principle underlying non-Hermitian topological systems, and paves the way for a complete understanding of topological matter in open systems.