A novel scheme for diagnosing non-stationary electrocardiogram (ECG) records using a combination of stochastic time-series detection and wavelet-based classification methods is presented. The ECG diagnosis algorithm stems from a two-stage procedure, which initially detects and subsequently classifies ECG segments bearing cardiac abnormalities. In the first stage, recursive stochastic time-series representations (as applied to fault diagnosis of mechanical systems) are used for detecting any potentially abnormal heartbeat incidents in the ECG signal. During the second stage, the detected incidents are fed into a wavelet classifier, which assigns the corresponding heartbeats to different classes, i.e. Supraventricular, Ventricular, Fusion and Normal. The resulting classification task is thus focused on abnormal ECG segments, as the segments related to healthy heart status are discarded by the detection step. The scheme's performance is evaluated on several ECG recordings from the MIT-BIH Arrhythmia database. Despite minimal preprocessing of the ECG recordings and the simplicity of the ECG features extraction scheme with respect to other well-established schemes, the algorithmic performance is comparable.