A novel technique is developed to process nanocrystalline Ca3Co4O9 ceramics with much enhanced thermoelectric properties. Nanocrystalline Ca3Co4O9 nanofibers are synthesized first using sol-gel based electrospinning, and then consolidated into bulk ceramics by spark plasma sintering with preferred grain orientation distribution and without substantial grain growth. The nanofiber-sintered ceramic has a grain size much smaller than that sintered from sol-gel synthesized powders with improved texture, and has simultaneously enhanced Seebeck coefficient, electric conductivity, and thermal resistivity, resulting in substantial enhancement in thermoelectric figure of merit ZT. This technique is promising for high-efficiency thermoelectric conversion of waste heat directly into electricity.