A formula is derived for the prediction of the average velocity of a solitary coarse grain moving over a rigid flat channel bed. To verify the theoretical consideration, data collected in the present study and reported in the literature (811 sets in total) are analyzed for typical bed roughness configurations. The results show significant improvements in the prediction of solitary grain velocity for both smooth- and rough-bed conditions in comparison with other formulas available in the literature. From the proposed formula, it follows that for rough-bed conditions, the dimensionless grain velocity depends on the Shields number and also the ratio of bed-roughness height to the grain diameter. The present study is limited to motion of solitary grains, but the result obtained implies that bed-load transport rate could be also affected by the equivalent bed-roughness height even under mobile bed conditions and such effects may become pronounced for nonuniform sediments.