The structure evolution of fluorinated graphite (CF_x) upon the Li/Na intercalation has been studied by first-principles calculations. The Li/Na adsorption on single CF layer and intercalated into bulk CF have been calculated. The better cycling performance of Na intercalation into the CF cathode, comparing to that of Li intercalation, is attributed to the different strength and characteristics of the Li-F and Na-F interactions. The interactions between Li and F are stronger and more localized than those between Na and F. The strong and localized Coulomb attraction between Li and F atoms breaks the C−F bonds and pulls the F atoms away, and graphene sheets are formed upon Li intercalation.