Classical nucleation theory offers a good framework for understanding the common features of new phase formation processes in metastable homogeneous media at rest. However, nucleation processes in liquids are ubiquitously affected by hydrodynamic flow, and there is no satisfactory understanding of whether shear promotes or slows down the nucleation process. We developed a classical nucleation theory for sheared systems starting from the molecular level of the Becker-Doering master kinetic equation and we analytically derived a closed-form expression for the nucleation rate. The theory accounts for the effect of flow-mediated transport of molecules to the nucleus of the new phase, as well as for the mechanical deformation imparted to the nucleus by the flow field. The competition between flow-induced molecular transport, which accelerates nucleation, and flow-induced nucleus straining, which lowers the nucleation rate by increasing the nucleation energy barrier, gives rise to a marked nonmonotonic dependence of the nucleation rate on the shear rate. The theory predicts an optimal shear rate at which the nucleation rate is one order of magnitude larger than in the absence of flow.