This contribution presents an early-time solution for permeability evaluation in pulse-decay tests. A nonlinear governing equation for gas transport in the sample is derived with consideration of the pressure dependence of gas compressibility and slippage effect, and the early-time solution is obtained through the integral balance analysis. The permeability coefficient can be determined by the proposed solution through the pressure transients within the early-time stage of the tests, i.e. before the upstream pressure pulse penetrates through the core sample and reaches the downstream side. To validate the proposed solution, measurements were performed on a core sample of the Cretaceous Eagle Ford shale, Texas, USA, under different pore and confining pressures. Helium was used as the test fluid to minimize the Joule-Thomson effect and adsorption. The experimental results show that the permeability coefficients obtained from this new solution agree well with those from the late-time solution, and prove our solution an accurate and efficient way for permeability evaluation. The present approach provides a good supplement for the pulse-decay method and suitable for measurements of ultra-low-permeability rocks.