Cabomba gracilis is a fossil species of aquatic plant in the family Cabombaceae.
The slender, smooth stems bear opposite, dichotomously branched submerged leaves with linear or filiform segments.
It was published by John Strong Newberry in 1883. The fossil was collected by Dr. Hayden in Fort Union, North Dakota, USA.
The specific epithet gracilis means graceful.