In PRL 116 (2016) no.6, 062001, the space of planar pentagon functions that describes all two-loop on-shell five-particle scattering amplitudes was introduced. In the present paper we present a natural extension of this space to non-planar pentagon functions. This provides the basis for our pentagon bootstrap program. We classify the relevant functions up to weight four, which is relevant for two-loop scattering amplitudes. We constrain the first entry of the symbol of the functions using information on branch cuts. Drawing on an analogy from the planar case, we introduce a conjectural second-entry condition on the symbol. We then show that the information on the function space, when complemented with some additional insights, can be used to efficiently bootstrap individual Feynman integrals. The extra information is read off of Mellin-Barnes representations of the integrals, either by evaluating simple asymptotic limits, or by taking discontinuities in the kinematic variables. We use this method to evaluate the symbols of two non-trivial non-planar five-particle integrals, up to and including the finite part.