We study the stability of relativistic stars in scalar-tensor theories with a nonminimal coupling of the form $F(phi)R$, where $F$ depends on a scalar field $phi$ and $R$ is the Ricci scalar. On a spherically symmetric and static background, we incorporate a perfect fluid minimally coupled to gravity as a form of the Schutz-Sorkin action. The odd-parity perturbation for the multipoles $l geq 2$ is ghost-free under the condition $F(phi)>0$, with the speed of gravity equivalent to that of light. For even-parity perturbations with $l geq 2$, there are three propagating degrees of freedom arising from the perfect-fluid, scalar-field, and gravity sectors. For $l=0, 1$, the dynamical degrees of freedom reduce to two modes. We derive no-ghost conditions and the propagation speeds of these perturbations and apply them to concrete theories of hairy relativistic stars with $F(phi)>0$. As long as the perfect fluid satisfies a weak energy condition with a positive propagation speed squared $c_m^2$, there are neither ghost nor Laplacian instabilities for theories of spontaneous scalarization and Brans-Dicke (BD) theories with a BD parameter $omega_{rm BD}>-3/2$ (including $f(R)$ gravity). In these theories, provided $0<c_m^2 le 1$, we show that all the propagation speeds of even-parity perturbations are sub-luminal inside the star, while the speeds of gravity outside the star are equivalent to that of light.