Thermoelectric materials have attracted much more attention due to their wide applications. In comparison with thermoelectric alloys, oxide semiconductors, which are thermally and chemically stable in air at high temperature, are regarded as the candidates for high-temperature thermoelectric applications. We prepared nanostructured p-type BiCuSeO and n-type In2O3-based ceramics by Spark plasma sintering. Our results indicate that the nano-grained size and band gap engineering can effective scatter the low and mid-frequency phonons to smaller than grain size, resulting in 50% reduction of thermal conductivity compared with that of the 2 μm grained sample, and ZT can be enahnced greatly. A high performance thermoelectric oxyselenide BiCuSeO ceramic with ZT>1.5 at 823 K is obtained. The band gap engineering and nanostructures can effectively tune its electronic structure, hole concentration and thermal conductivity, resulting in substantially enhanced mobility, power factor and thus ZT value.