Improving the thermal conductivity of zeolite adsorbents is essential for enhancing the efficiency of thermal swing adsorption (TSA) processes in CO2 capture. In this work, zeolite Y was combined with two types of carbon-based thermal conductive enhancers, expanded natural graphite (ENG) and graphene nanosheets (GRA), to form zeolite–carbon composites. Structural analysis confirmed that the incorporation of carbon additives did not damage the zeolite framework, although the addition of non-porous carbon led to a decrease in surface area and micropore volume. Measurements with a transient hot disk method revealed that the incorporation of ENG and GRA could remarkably enhance the thermal conductivity of zeolite Y-carbon composites. A 7-fold increase in thermal conductivity, from 0.107 to 0.762 Wm−1K−1, was achieved by adding 5wt.% of GRA, whereas a comparable improvement with ENG required a much higher loading of about 30 wt.%. Infrared thermography on packed composite powder on a heated plate indicated that the heat transfer through the composites with improved thermal conductivity is significantly faster compared to plain zeolite. CO2 adsorption measurements indicated that both additives reduced the CO2 uptake capacity, but the loss was significantly smaller for the graphene composites (at 5 wt.% addition), which retained most of the micropore volume. Ideal adsorbed solution theory calculations further showed that the zeolite Y-GRA composites maintained reasonably high CO2/N2 selectivity, though lower than pristine zeolite Y. In conclusion, the zeolite–graphene composites present a promising pathway to improve the intrinsic thermal limitations of zeolite sorbents, enabling faster heating and cooling cycles and improved productivity in TSA-based carbon capture systems.