In this paper we study optimal stopping problems with respect to distorted expectations of the form \begin{eqnarray*} \mathcal{E}(X)=\int_{-\infty}^{\infty} x\,dG(F_X(x)), \end{eqnarray*} where $F_X$ is the distribution function of $X$ and $G$ is a convex distribution function on $[0,1].$ As a matter of fact, except for $G$ being the identity on $[0,1],$ dynamic versions of $\mathcal{E}(X)$ do not have the so-called time-consistency property necessary for the dynamic programming approach. So the standard approaches are not applicable to optimal stopping under $\mathcal{E}(X).$ In this paper, we prove a novel representation, which relates the solution of an optimal stopping problem under distorted expectation to the sequence of standard optimal stopping problems and hence makes the application of the standard dynamic programming-based approaches possible. Furthermore, by means of the well known Kusuoka representation, we extend our results to optimal stopping under general law invariant coherent risk measures. Finally, based on our novel representations, we develop several Monte Carlo approximation algorithms and illustrate their power for optimal stopping under Average Value at Risk and the absolute semideviation risk measures.