The Hall-Yarborough equation (H-Y equation) of state has been favoured in natural gas engineering due to its accuracy and conciseness for many years. In this paper, the Adomian decomposition method (ADM) is employed to devise a novel algorithm for calculating the compressibility factors of natural gases through this reliable equation of state. A convergence accelerator technique, namely the efficient Shanks transform, is also exploited to further improve our scheme in terms of computational speed. Unlike most of the previous numerical solution strategies, our algorithm does not require an initial guess as the starting point and is computationally efficient. The proposed algorithm is found to be superior over the common Newton-Raphson algorithm, where we have also demonstrated that the latter can easily lead to grossly erroneous solutions. For the sake of illustration, a number of real-world case study problems are solved by our algorithm and relevant comparisons are provided.