Computational materials science has the potential to lead the search for novel, highly efficient, sustainably sourced, non-toxic materials for thermoelectric applications. Such materials are required for next generation devices to transform global energy generation and conversion. Key to reaching this potential is the development of suitable techniques to be applied in a tractable manner. Here we present our computational design approach to realising new thermoelectric materials. We discuss methodology, and demonstrate a fully ab initio computational scheme to determine accurate figures of merit, including precise calculations of thermal transport properties. The effects of disorder and reduced dimensionality, which are crucial to limiting the thermal conductivity, are key considerations in our materials design programme. Moreover, we calculate the defect properties of the materials of interest, which allows us to determine their n- and p-type characteristics, and pinpoint suitable dopants. We present results on several systems, including a new Bi-containing oxide that has the potential to be a major low-cost alternative to current thermoelectrics. Our work is facilitated by close collaboration with experimentalists, whose results, which confirm our conclusions, we present and discuss.