BACKGROUND: Atrial fibrillation (AF) is a disorder of the heart rhythm where irregular and rapid heartbeats are observed. This supraventricular arrhythmia may increase the risk of blood clots, stroke, heart failure, and other serious heart complications. Automatic analysis of AF that is based on machine learning (ML) plays an important role in detecting this heart disease. METHODS: A new approach for automated AF detection is presented using heart rate variability (HRV) features and machine learning. A set of time-domain, frequency-domain and nonlinear features are extracted from the R-R intervals. A new method for frequency-domain analysis of R-R intervals using the Fourier Decomposition Method is presented, which provides promising results as compared to the usual method of power spectral density estimation. We train the algorithm on the Massachusetts Institute of Technology-Beth Israel Hospital (MIT-BIH) atrial fibrillation database and perform a comprehensive analysis using statistical tests to obtain the results without any intra-patient bias. RESULTS: The proposed method is able to achieve average result of 95.16% sensitivity, 92.46% specificity and 94.43% accuracy and its performance is better than the existing approaches. Furthermore, the efficacy of the proposed algorithm is tested on eight records from a previously unseen MIT-BIH Arrhythmia Database. CONCLUSION: This work shows that the proposed HRV features and ML approach can be effectively used for the analysis, detection, and classification of AF.