We consider perpetual American options, assuming that under a chosen equivalent martingale measure the stock returns follow a Levy process. For put and call options, their analogues for more general payoffs, and a wide class of Levy processes that contains Brownian motion, normal inverse Gaussian processes, hyperbolic processes, truncated Levy processes, and their mixtures, we obtain formulas for the optimal exercise price and the fair price of the option in terms of the factors in the Wiener-Hopf factorization formula, i.e., in terms of the resolvents of the supremum and in mum processes, and derive explicit formulas for these factors. For calls, puts, and some other options, the results are valid for any Levy process. We use Dynkin's formula and the Wiener-Hopf factorization to find the explicit formula for the price of the option for any candidate for the exercise boundary, and by using this explicit representation, we select the optimal solution. We show that in some cases the principle of the smooth fit fails and suggest a generalization of this principle.