In the present study, the Lattice Boltzmann Method (LBM) is applied to simulate the flow of non-Newtonian shear-thinning fluids in three-dimensional digitally reconstructed porous domains. The non-Newtonian behavior is embedded in the LBM through a dynamical change of the local relaxation time. The relaxation time is related to the local shear rate in such a way that the power law rheology is recovered. The proposed LBM is applied to the study of power-law fluids in ordered sphere packings and stochastically reconstructed porous domains. A linear relation is found between the logarithm of the average velocity and the logarithm of the body force with a curve slope approximately equal to the inverse power-law index. The validity of the LBM for the flow of shear thinning fluids in porous media is also tested by comparing the average velocity with the well known semi-empirical Christopher-Middleman correlation. Good agreement is observed between the numerical results and the Christopher-Middleman correlation, indicating that the LBM combined with digital reconstruction constitutes a powerful tool for the study of non-Newtonian flow in porous media.