Potassium-ion batteries (PIBs) are attractive for low-cost and large-scale energy storage applications, in which graphite is one of the most promising anodes. However, the large size and the high activity of K+ ions and the highly catalytic surface of graphite largely prevent the development of safe and compatible electrolytes. Here, a nonflammable, moderate-concentration electrolyte is reported that is highly compatible with graphite anodes and that consists of fire-retardant trimethyl phosphate (TMP) and potassium bis(fluorosulfonyl)imide (KFSI) in a salt/solvent molar ratio of 3:8. It shows unprecedented stability, as evidenced by its 74% capacity retention over 24 months of cycling (over 2000 cycles) at the 0.2 C current rate. Electrolyte structure and surface analyses show that this excellent cycling stability is due to the nearly 100% solvation of TMP molecules with K+ cations and the formation of FSI−-derived F-rich solid electrolyte interphase (SEI), which effectively suppresses the decomposition of the solvent molecules toward the graphite anode. Furthermore, excellent performance on high-mass loaded graphite electrodes and in a full cell with perylenetetracarboxylic dianhydride cathode is demonstrated. This study highlights the importance of the compatibility of both electrolyte and the interface, and offers new opportunities to design the electrolyte–SEI nexus for safe and practical PIBs.