The story
Ellipsis of earlier French fried potatoes (1856) and French-fried potatoes, potatoes supposedly prepared in the French style. The idea that the preparation was specific to French cuisine was more notional than otherwise; more at Wikipedia. Compare also French dressing.
First known use, by meaning
- from 1903 Strips of potato that have been deep-fried.
Etymology from Wiktionary, CC BY-SA 4.0.