A remarkable zone of Tehran, capital of Iran, is composed of coarse-grained and cemented soils. These deposits mostly comprise gravel in company with variable amount of cobble and sand in addition to silt and clay. The style of stiffness variation of these kinds of soils versus confining pressure (depth) and strain has been studied in previous researches less often. To determine the form in which Tehran stiffness changes with depth and strain, Pressuremeter and shear wave velocity tests have been performed in this study. The results show that the stiffness of Tehran soil in small strains is considerably higher than stiffness of most gravelly soils reported in technical literature. A unique trend was observed in increase of soil stiffness with depth or confining pressure at several points of Tehran. Nonlinear stiffness reduction of A and C alluvium sediments of Tehran cannot be presented by Fahey-Carter model appropriately. By review of other coarse-grained soils stiffness, it was observed that the behavior of gravelly soils with high percentage of gravel, over consolidated coarse-grained soils, pre-strained coarse-grained soils and cemented soils are similar to Tehran soil. The specific behavior of Tehran soil and its dissimilarity to other coarse-grained soils is relevant to its cementation and over consolidation. The stiffness reduction curves of mentioned soils that were contradicting with Fahey-Carter model were compared with Ramberg-Ozgood model and observed that Ramberg-Ozgood model has a high capability of modeling nonlinear behavior of these kinds of soils. By combination of Fahey-Carter model and Ramberg-Ozgood model, a new model has been proposed which can present all possible stiffness reduction curves of coarse-grained soils in G/G_max – τ/τ_max space appropriately. Moreover, physical concepts have been presented for the new model parameters and their relevance to different variables has been determined.