FeWO4 (FWO) nanocrystals were prepared at 180 °C by a simple hydrothermal method, and carbon-coated FWO (FWO/C) was obtained at 550 °C using pyrrole as a carbon source. The FWO/C obtained from the product hydrothermally treated for 5 h exhibits reversible capacities of 771.6, 743.8, 670.6, 532.6, 342.2, and 184.0 mAh g(-1) at the current densities of 100, 200, 400, 800, 1600, and 3200 mA g(-1), respectively, whereas that from the product treated for 0.5 h achieves a reversible capacity of 205.9 mAh g(-1) after cycling 200 times at a current density of 800 mA g(-1). The excellent electrochemical performance of the FWO/C results from the combination of the nanocrystals with good electron transport performance and the nitrogen-doped carbon coating.