We use ab initio total-energy calculations to predict the existence of polarons in semiconducting carbon nanotubes (CNTs). We find that the CNTs band edge energies vary linearly and the elastic energy increases quadratically with both radial and with axial distortions, leading to the spontaneous formation of polarons. Using a continuum model parametrized by the ab initio calculations, we estimate electron and hole polaron lengths, energies and effective masses and analyze their complex dependence on CNT geometry. Implications of polaron effects on recently observed electro- and opto-mechanical behavior of CNTs are discussed.