Potassium-ion batteries are a promising alternative to lithium-ion batteries. However, it is challenging to achieve fast charging/discharging and long cycle life with the current electrode materials because of the sluggish potassiation kinetics. Here we report a soft carbon anode, namely highly nitrogen-doped carbon nanofibers, with superior rate capability and cyclability. The anode delivers reversible capacities of 248 mAh g-1 at 25 mA g-1 and 101 mAh g-1 at 20 A g-1, and retains 146 mAh g-1 at 2 A g-1 after 4000 cycles. Surface-dominated K-storage is verified by quantitative kinetics analysis and theoretical investigation. A full cell coupling the anode and Prussian blue cathode delivers a reversible capacity of 195 mAh g-1 at 0.2 A g-1. Considering the cost-effectiveness and material sustainability, our work may shed some light on searching for K-storage materials with high performance.