We have designed a unique microstructure of graphene embedded LiFePO4 by a catalyst assisted self assembly method as a cathode material for high power lithium-ion batteries. The stable amide bonds between LiFePO4 and graphene were formed by the catalyst assisted self assembly. High conductive graphene provides a fast electron transfer path, and many pores inside the structure facilitate the lithium-ion diffusion. The graphene embedded LiFePO4 fabricated by the novel method shows enhanced cycling performance and rate-capability compared with that of carbon coated LiFePO4 as a cathode material for high power lithium-ion batteries.