Recently, physically-based hydrological models have been gaining much popularity in various activities of water resources planning and management, such as assessment of basin water availability, floods, droughts, and reservoir operation. Every hydrological model contains some parameters that must be tuned to the catchment being studied to obtain reliable estimates from the model. This study evaluated the performance of different evolutionary algorithms, namely genetic algorithm (GA), shuffled complex evolution (SCE), differential evolution (DE), and self-adaptive differential evolution (SaDE) algorithm for the parameter calibration of a computationally intensive distributed hydrological model, variable infiltration capacity (VIC) model. The methodology applied and tested for a case study of the upper Tungabhadra River basin in India and the performance of the algorithms is evaluated in terms of reliability, variability, efficacy measures in a limited number of function evaluations, their ability for achieving global convergence, and also by their capability to produce a skilful simulation of streamflows. The results of the study indicated that SaDE facilitates an effective calibration of the VIC model with higher reliability and faster convergence to optimal solutions as compared to the other methods. Moreover, due to the simplicity of the SaDE, it provides easy implementation and flexibility for the automatic calibration of complex hydrological models.