Skutterudite materials are widely considered for thermoelectric waste heat recovery. While the skutterudite structure effectively scatters the high frequency phonons, grain-boundary engineering is needed to further reduce the thermal conductivity beyond simply decreasing grain size. Here, we show that reduced graphene oxide (rGO) increases the grain boundary thermal resistivity by a factor of 3 to 5 compared to grain boundaries without graphene. Wrapping even micron sized grains with graphene leads to such a significant reduction in the thermal conductivity that a high thermoelectric figure of merit zT = 1.5 was realized in n-type YbyCo4Sb12, while a zT of 1.06 was achieved in p-type CeyFe3CoSb12. A 16 leg thermoelectric module was made by using n-and p-type skutterudite-graphene nanocomposites that exhibited conversion efficiency 24% higher than a module made without graphene. Engineering grain boundary complexions with 2-D materials introduces a new strategy for advanced thermoelectric materials.