Stochastic global optimization methods have been successfully used to perform phase stability calculations. However, these methods may show some drawbacks in challenging phase stability problems. In this study, we made use of the gradient of the tangent plane distance function to improve the performance of Cuckoo Search (CS) algorithm, which is a promising nature-inspired stochastic global optimization method, for the calculation of phase stability analysis. The new modified algorithm, Gradient-Based Cuckoo Search (GBCS), was evaluated for solving several challenging phase stability problems. Its performance at different numerical effort levels and the effect of stopping criterion have been analyzed. GBCS was found to perform better than the original CS algorithm. In comparison with other stochastic optimization methods using an improvement objective function-based stopping criterion, GBCS proved to be the most reliable without any reduction in efficiency. (C) 2014 Elsevier B.V. All rights reserved.