Bacteria exhibit a bewildering diversity of morphologies, but despite their impact on nearly all aspects of life, they are frequently classified into a few general categories, usually just “spheres” and “rods.” Curved-rod bacteria are one simple variation observed in many environments, particularly the ocean. However, why so many species have evolved this shape is unknown. We used a regularized Stokeslet Boundary Element Method to model the motility of flagellated, curved bacteria. We show that curvature can increase swimming efficiency, revealing a widely applicable selective advantage. Furthermore, we show that the distribution of cell lengths and curvatures observed across bacteria in nature is predicted by evolutionary trade-offs between three tasks influenced by shape: efficient swimming, the ability to detect chemical gradients, and reduced cost of cell construction. We therefore reveal shape as an important component of microbial fitness.