A theoretical and computational study analysing the initiation of yield-stress fluids percolation in porous media is presented. Yield-stress fluid flows through porous media are complicated due to the non-linear rheological behaviour of this type of fluids, rendering the conventional Darcy type approach invalid. A critical pressure gradient must be exceeded to commence the flow of a yield-stress fluid in a porous medium. As the first step in generalising the Darcy law for yield-stress fluids, a universal scale based on the variational formulation of the energy equation is derived for the critical pressure gradient which reduces to purely geometrical feature of the porous media. The presented scaling is then validated by both exhaustive numerical simulations (using an adaptive finite element approach based on the augmented Lagrangian method), and also the previously published data. The considered porous media is constructed by randomised obstacles with various topologies; namely, square, circular and alternatively polygonal obstacles which are mimicked based on Voronoi tessellation of circular cases. Moreover, computations for the bi-dispersed obstacle cases are performed which further demonstrate the validity of the proposed universal scaling.