Transparent oxides are essential building blocks to many technologies, ranging from components in transparent electronics, transparent conductors, to absorbers and protection layers in photovoltaics and photoelectrochemical devices. However, thus far
, it has been difficult to develop p-type oxides with wide band gap and high hole mobility; current state-of-art transparent p-type oxides have hole mobility in the range of < 10 cm$^2$/Vs, much lower than their n-type counterparts. Using high-throughput computational screening to guide the discovery of novel oxides with wide band gap and high hole mobility, we report the computational identification and the experimental verification of a bismuth-based double-perovskite oxide that meets these requirements. Our identified candidate, Ba$_2$BiTaO$_6$, has an optical band gap larger than 4 eV and a Hall hole mobility above 30 cm$^2$/Vs. We rationalize this finding with molecular orbital intuitions; Bi$^{3+}$ with filled s-orbitals strongly overlap with the oxygen p, increasing the extent of the metal-oxygen covalency and effectively reducing the valence effective mass, while Ta$^{5+}$ forms a conduction band with low electronegativity, leading to a high band gap beyond the visible range. Our concerted theory-experiment effort points to the growing utility of a data-driven materials discovery and the combination of both informatics and chemical intuitions as a way to discover future technological materials.