© 2018, The Author(s). High-dimensional encoding of quantum information provides a way of transcending the limitations of current approaches to quantum communication, which are mostly based on the entanglement between qubits—two-dimensional quantum systems. One of the central challenges in the pursuit of high-dimensional alternatives is ascertaining the presence of high-dimensional entanglement within a given high-dimensional quantum state. In particular, it would be desirable to carry out such entanglement certification without resorting to inefficient full state tomography. Here, we show how carefully constructed measurements in two bases (one of which is not orthonormal) can be used to faithfully and efficiently certify bipartite high-dimensional states and their entanglement for any physical platform. To showcase the practicality of this approach under realistic conditions, we put it to the test for photons entangled in their orbital angular momentum. In our experimental set-up, we are able to verify 9-dimensional entanglement for a pair of photons on a 11-dimensional subspace each, at present the highest amount certified without any assumptions on the state.