In this paper we present new methods to estimate the effective permeability (k_eff) of heterogeneous porous media with a wide distribution of permeabilities and various underlying structures, using percolation concepts. We first set a threshold permeability (k_th) on the permeability density function (pdf) and use standard algorithms from percolation theory to check whether the high permeable grid blocks (i.e. those with permeability higher than k_th) with occupied fraction of “p” first forms a cluster connecting two opposite sides of the system in the direction of the flow (high permeability flow pathway). Then we estimate the effective permeability of the heterogeneous porous media in different ways: a power law (k_eff=k_th p^m), a weighted power average (k_eff=[p.k_th^m+(1-p).k_g^m ]^(1/m) with k_g the geometric average of the permeability distribution) and a characteristic shape factor multiplied by the permeability threshold value. We found that the characteristic parameters (i.e. the exponent “m”) can be inferred either from the statistics and properties of percolation sub-networks at the threshold point (i.e. high and low permeable regions corresponding to those permeabilities above and below the threshold permeability value) or by comparing the system properties with an uncorrelated random field having the same permeability distribution. These physically based approaches do not need fitting to the experimental data of effective permeability measurements to estimate the model parameter (i.e. exponent m) as is usually necessary in empirical methods. We examine the order of accuracy of these methods on different layers of 10th SPE model and found very good estimates as compared to the values determined from the commercial flow simulators.