The effects of carbon fiber additions on the electrical and thermoelectric performance in p-type CoSb3-based skutterudite are reported. A threefold enhancement in electrical conductivity is found. Two different explanations for the increased electrical conductivity are considered: Either carbon atoms enter the CoSb3 lattice as a dopant that makes it more and more conductive, or the increase in conductivity is due to electrical percolation of the carbon fibers in the composite. X-ray diffraction data show that the lattice parameter of the CoSb3 is not affected by the presence of the carbon fiber; however, adding carbon is associated with precipitation of 20 wt. % elemental Sb. DFT calculations show that the enthalpy of formation of a solid solution of carbon (interstitial or as a substitution for Sb) is slightly positive. This would be offset by an increased entropy contribution at higher temperatures, so the free energy change overall is likely to be favorable. All of the results support an explanation based on an improved electrical conductivity of a very dilute solid solution of C in CoSb3. The average thermoelectric parameters of the composite material, including heat conductivity, average composite Seebeck coefficient, Hall effect, carrier mobility, and carrier concentration, were influenced by the carbon addition. Unfortunately, the effects largely cancel each other so that the overall zT of the composite was not improved.