A thermoelectric material consisting of Cu2Se incorporated with up to 0.45 wt% of graphene nanoplates is reported. The carbon-reinforced Cu2Se exhibits an ultra-high thermoelectric figure-of-merit of zT = 2.44 ± 0.25 at 870 K. Microstructural characterization reveals dense, nanostructured grains of Cu2Se with multilayer-graphene and graphite agglomerations located at grain boundaries. High temperature X-ray diffraction shows that the graphene incorporated Cu2Se matrix retains a cubic structure and the composite microstructure is chemically stable. Based on the experimental structure, density functional theory was used to calculate the formation energy of carbon point defects and the associated phonon density of states. The isolated carbon inclusion is shown to have a high formation energy in Cu2Se whereas graphene and graphite phases are enthalpically stable relative to the solid solution. Neutron spectroscopy proves that there is a frequency mismatch in the phonon density of states between the carbon honeycomb phases and cubic Cu2Se. This provides a mechanism for the strong scattering of phonons at the composite interfaces, which significantly impedes the conduction of heat and enhances thermoelectric performance.