Nonlinear free vibration analysis of prestressed circular cylindrical shells placed on Winkler/Pasternak foundation is investigated in the present paper. The nonlinearity is considered due to large deflections. Simultaneous effects of prestressed condition and elastic foundation on natural frequencies of the shells under various boundary conditions are examined extensively in this study. The nonlinear Sanders-Koiter shell theory is employed in order to derive strain-displacement relationships. The nonlinear classical Love's thin shell theory is also applied in some specific cases due to contrast the results. Beam modal functions are used to approximate spatial displacement field. The governing equations in linear state are solved by the Rayleigh-Ritz procedure. Perturbation methods are used to find the relationship between vibration amplitude and frequency in nonlinear state. Prestress state includes the effects of internal hydrostatic pressure and initial uniaxial tension. Results are compared with published theoretical and experimental data for some specific cases.