In this paper, we present a fully automated technique for robust detection of Atrial Fibrillation (AF) episodes in single-lead electrocardiogram (ECG) signals using discrete-state Markov models and Random Forests. Methods: The ECG signal is first preprocessed using Stationary Wavelet Transforms (SWT) for noise suppression, signal quality assessment and subsequent R-peak detection. Discrete-state Markov probabilities modelling transitions between successive RR intervals along with other statistical quantities derived from the RR-interval series constitute the feature set to perform AF classification using Random Forests. Further enhancement in AF detection is achieved by using a post-processing false positive suppression algorithm based on autocorrelation analysis of the RR-interval series. Datasets: The AF classifier was trained using the Physionet/Computing in Cardiology 2017 AF Challenge dataset and the Atrial Fibrillation Termination Database (AFTDB). The test datasets consist of the MIT-BIH Atrial Fibrillation Database (AFDB) and the MIT-BIH Arrhythmia Database (MITDB). Results: Our algorithms achieved sensitivity, specificity and F-score values of 97.4%, 98.6% and 97.7% respectively on the AFDB dataset and 96.3%, 97.0% and 85.6% respectively on the MITDB dataset. It was also observed that inclusion of the false positive suppression step resulted in a 1.1% increase in specificity and a 4.0% increase in F-score for the MITDB dataset without any decrease in sensitivity. Conclusion: The proposed method of AF detection, combining Markov models and Random Forests, achieves high accuracy across multiple databases and demonstrates comparable or superior performance to several other state-of-the-art algorithms.