Filling the voids of cage forming compounds with loosely bound electropositive elements and by incorporating nano-sized secondary phases are promising approaches to enhance the thermoelectric figure of merit of these materials. Hence, in this work, by combining these two approaches-inserting In into the voids of skutterudite Co4Sb12 as well as dispersing nanoparticles (GaSb)-we have synthesized various samples via ball-milling and spark plasma sintering. InSb as the secondary phase of the matrix, mixed with GaSb, forms the solid solution Ga1-xInxSb. Nanocrystalline grains together with a few larger grains (10-30 μm) are found to be spread in In0.2Co4Sb12. The former is comprised of either InSb, GaSb or Ga1-xInxSb. Because of their identical space group and similar lattice parameters, InSb, GaSb and Ga1-xInxSb could not be detected separately in EBSD. High resolution transmission electron microscopy (HRTEM) was used to resolve different phases, which showed GaSb grains of size ∼10-30 nm and InSb grains of size ∼30-100 nm. Scattering of charge carriers at the interfaces of InSb, GaSb and Ga1-xInxSb as well as the matrix phases increased both the electrical resistivity and Seebeck coefficient. The multi-scale size distribution of grains, of both the matrix phase and the secondary phases, scattered phonons within a broad wavelength range, resulting in very low lattice thermal conductivities. As a result, an enhanced figure of merit of 1.4 was achieved for the (GaSb)0.1 + In0.2Co4Sb12 nanocomposite at 773 K.