A novel Strain Hardening Cementitious Composite (SHCC) was developed by incorporating ultra-fine (30 μm) phase change materials (PCMs) composites and Graphene Oxide (GO) to enhance its mechanical and thermal performance. The ultra-fine PCMs composites were fabricated by intruding 75.0 wt % of paraffin (PA) into 25.0% of expanded perlite (EP) using the vacuum impregnation method. The ultra-fine PCMs can be used as ultra-fine aggregates to improve the composites’ thermal properties without compromising the compressive strength, due to the micro-filler effect and pozzolanic properties of the PCMs composites. GO was introduced to further improve the tensile and flexural performance and the mechanisms involved are comprehensively discussed. Regarding thermal properties, the addition of ultra-fine PCMs composites not only reduced the thermal conductivity by 56.6% but also improved the specific heat capacity and thermal insulation properties of the SHCC, which enabled the structural concrete members with the integration of load-bearing and indoor temperature control. In conclusion, a novel SHCC with enhanced thermal and mechanical properties by adding ultra-fine PCMs composites and GO shows a great potential for green buildings with the integration of structure, energy conservation and durability.