Phase change material (PCM) is a kind of thermal energy storage material. Solid-liquid PCM composite materials must overcome the issues of material leakage and low thermal conductivity before they are suitable for widespread use in the fields of building and industry. In this study, porous expanded graphite (EG) is used as a carrier, which absorbs the PCM to fabricate EG/paraffin composites (EG/P) containing 90.6% paraffin, and a latent heat of up to 105.3 J/g was measured. Because gypsum board is widely used in buildings, therefore, EG/P composites are suitable to be integrated into gypsum to develop expanded graphite/paraffin gypsum-based composite material (EGPG) for thermal energy storage. In order to optimize the performance of EGPG, carbon fiber (CF) is used to reinforce their thermal and mechanical properties. The test results show that when 1 wt % CF is incorporated into the EGPG, the thermal conductivity increased 36.0%, and thus EGPG shows superior thermal control through the significantly increased efficiency of heat transfer. After 1 wt % CF was added, the flexural and compressive strength of EGPG were increased by 65.6% and 6.4%, respectively. The improved thermal and mechanical performance of EGPG modified by CF demonstrates that it is a structural-functional integrated building material suitable for building envelope system.