In the packaging industry, the barrier property of packaging materials is of paramount importance. The enhancement of barrier properties of materials can be achieved by adding impermeable nanoparticles into thin polymeric films, known as mixed-matrix membranes (MMMs). Three-dimensional numerical simulations were performed to study the barrier property of these MMMs and to estimate the effective membrane gas permeability. Results show that horizontally-aligned thin cuboid nanoparticles offer far superior barrier properties than spherical nanoparticles for an identical solid volume fraction. Maxwell’s model predicts very well the relative permeability of spherical and cubic nanoparticles over a wide range of the solid volume fraction. However, Maxwell’s model shows an increasingly poor prediction of the relative permeability of MMM as the aspect ratio of cuboid nanoparticles tends to zero or infinity. An artificial neural network (ANN) model was developed successfully to predict the relative permeability of MMMs as a function of the relative thickness and the relative projected area of the embedded nanoparticles. However, since an ANN model does not provide an explicit form of the relation of the relative permeability with the physical characteristics of the MMM, a new model based on multivariable regression analysis is introduced to represent the relative permeability in a MMM with impermeable cuboid nanoparticles. The new model possesses a simple explicit form and can predict, very well, the relative permeability over an extensive range of the solid volume fraction and aspect ratio, compared with many existing models.