  The discovery of superconductivity in CaC6 with a critical temperature (Tc)
of 11.5 K reignites much interest in exploring high-temperature
superconductivity in graphite intercalation compounds (GICs). Here we identify
a GIC NaC4, discovered by ab initio evolutionary structure search, as a
superconductor with a computed Tc of 41.2 K at 5 GPa. This value is eight times
higher than that of the synthesized GIC NaC2 and possesses the highest Tc among
available GICs. The remarkable superconductivity of GIC NaC4 mainly arises from
the coupling of {\pi} electrons in graphene with the low-frequency vibrations
involving both Na and C atoms. These findings suggest that Na-GICs may hold
great promise as high-Tc superconductors.
