In this paper, we introduce an estimation of the random Klinkenberg slip coefficient in the apparent permeability model using a chaos decomposition technique. The apparent permeability expression (Klinkenberg model) is used to describe natural gas transport in low-permeability media. In this process, the Klinkenberg factor is considered as a random parameter that depends on two random variables. The mean and variance (or standard deviation) of the two random variables can be estimated from the empirical data available in the literature. Therefore, the variation in the pressure is related directly to the random variation in the Klinkenberg factor. The polynomial chaos expansion is used to decompose the governing equation into a set of coupled deterministic equations that are solved and then used to compute the mean and variance of the solution. The algorithm of how to solve the deterministic coupled system is also presented. For verification, the model and its solution have been compared with the analytical solution of the basic steady-state version of the model. The comparison shows a very good agreement. The effects of a number of important parameters have been presented in graphs and discussed. It was found that the stochastic model works very well with small values of the liquid equivalent permeability, which meets the characteristics of low-permeability reservoirs. Also, the stochastic model works very well with small values of gas viscosity. On the other hand, the porosity seems to be not engaged well with the low-permeability model. The sensitivity of selection of random parameters is also investigated as well as the transient effect.