This work studies the permeability of power-law fluids in porous fibrous media with electrokinetic effects. By solving the linearized Poisson-Boltzmann and Navier-Stokes equations, we get the analytical solutions of pressure driven flow of power-law fluids in a microcapillary with electric double layer (EDL). The flow rate in a single capillary, combining with the fractal model of pore distribution of fractures in naturally fractured porous media, deduces the total flow rate. Then the analytical result of effective permeability for power-law fluids with EDL effects is derived as a function of the porosity, the flow behavior index and a dimensionless number derived from the solid surface zeta potential and maximum pore radius. The present results show that the EDL effects as well as other variable parameters may greatly influence the effective permeability of the power-law fluids in porous fibrous media: the larger the porosity, the higher the effective permeability; the larger the maximum pore radius, the higher the effective permeability; the higher the solid surface zeta potential, the more the EDL effects; the more the EDL effects, the lower the effective permeability. Comparing the effective permeability produced by different flow behavior indexes, we further illustrate that the EDL has virtually no effects when the flow behavior index is great than 1, moderate effects when equal to 1, and very significant effects when less than 1. Therefore the EDL effects may provide strong constraints on evaluation of the effective permeability of the shear thinning fluids rather than the shear thickening and Newtonian fluids. (C) 2015 Elsevier Ltd. All rights reserved.