As contemporary software-intensive systems reach increasingly large scale, it is imperative that failure detection schemes be developed to help prevent costly system downtimes. A promising direction towards the construction of such schemes is the exploitation of easily available measurements of system performance characteristics such as average number of processed requests and queue size per unit of time. In this work, we investigate a holistic methodology for detection of abrupt changes in time series data in the presence of quasi-seasonal trends and long-range dependence with a focus on failure detection in computer systems. We propose a trend estimation method enjoying optimality properties in the presence of long-range dependent noise to estimate what is considered 'normal' system behaviour. To detect change-points and anomalies, we develop an approach based on the ensembles of 'weak' detectors. We demonstrate the performance of the proposed change-point detection scheme using an artificial dataset, the publicly available Abilene dataset as well as the proprietary geoinformation system dataset.