This paper first proposes an effective modification for the gravitational search algorithm. The new strategy used an adaptive maximum velocity constraint, which aims to control the global exploration ability of the original algorithm, increase its convergence rate and thereby to obtain an acceptable solution with a lower number of iterations. We testify the performance of the modified gravitational search algorithm (MGSA) on a suite of five well-known benchmark functions and provide comparisons with standard gravitational search algorithm (SGSA). The simulated results illustrate that the modified GSA has the potential to converge faster, while improving the quality of solution. Thereafter, the proposed MGSA is employed to search for the minimum factor of safety and minimum reliability index in both deterministic and probabilistic slope stability analysis. The factor of safety is formulated using a concise approach of the Morgenstern and Price method and the advanced first-order second-moment (AFOSM) method is adopted as the reliability assessment model. The numerical experiments demonstrate that the modified algorithm significantly outperforms the original algorithm and some other methods in the literature.