In many Austrian catchments in recent decades an increase in the mean annual air temperature and precipitation has been observed, but only a small change in the mean annual runoff. The main objective of this paper is (1) to analyze alterations in the performance of a conceptual hydrological model when applied in changing climate conditions and (2) to assess the factors and model parameters that control these changes. A conceptual rainfall-runoff model (the TUW model) was calibrated and validated in 213 Austrian basins from 1981–2010. The changes in the runoff model’s efficiency have been compared with changes in the mean annual precipitation and air temperature and stratified for basins with dominant snowmelt and soil moisture processes. The results indicate that while the model’s efficiency in the calibration period has not changed over the decades, the values of the model’s parameters and hence the model’s performance (i.e., the volume error and the runoff model’s efficiency) in the validation period have changed. The changes in the model’s performance are greater in basins with a dominant soil moisture regime. For these basins, the average volume error which was not used in calibration has increased from 0% (in the calibration periods 1981–1990 or 2001–2010) to 9% (validation period 2001–2010) or –8% (validation period 1981–1990), respectively. In the snow-dominated basins, the model tends to slightly underestimate runoff volumes during its calibration (average volume error = –4%), but the changes in the validation periods are very small (i.e., the changes in the volume error are typically less than 1–2%). The model calibrated in a colder decade (e.g., 1981–1990) tends to overestimate the runoff in a warmer and wetter decade (e.g., 2001–2010), particularly in flatland basins. The opposite case (i.e., the use of parameters calibrated in a warmer decade for a colder, drier decade) indicates a tendency to underestimate runoff. A multidimensional analysis by regression trees showed that the change in the simulated runoff volume is clearly related to the change in precipitation, but the relationship is not linear in flatland basins. The main controlling factor of changes in simulated runoff volumes is the magnitude of the change in precipitation for both groups of basins. For basins with a dominant snowmelt runoff regime, the controlling factors are also the wetness of the basins and the mean annual precipitation. For basins with a soil moisture regime, landcover (forest) plays an important role.