The development of high performance transparent conducting oxides (TCOs) is critical to many technologies from transparent electronics to solar cells. While n-type TCOs are present in many devices, current p-type TCOs are not largely commercialized as they exhibit much lower carrier mobilities, due to the large hole effective masses of most oxides. Here, we conduct a high-throughput computational search on thousands of binary and ternary oxides and identify several highly promising compounds displaying exceptionally low hole effective masses (up to an order of magnitude lower than state of the art p-type TCOs) as well as wide band gaps. In addition to the discovery of specific compounds, the chemical rationalization of our findings opens new directions, beyond current Cu-based chemistries, for the design and development of future p-type TCOs.