Atrial fibrillation (AF) is usually detected by inspection of the electrocardiogram waveform, a task made difficult when the signal is distorted by noise. The RR interval time series is more frequently available and accurate, yet linear and nonlinear time series analyses that detect highly varying and irregular AF are vulnerable to the common finding of frequent ectopy. We hypothesized that different nonlinear measures might capture characteristic features of AF, normal sinus rhythm (NSR), and sinus rhythm (SR) with frequent ectopy in ways that linear measures might not. To test this, we studied 2722 patients with 24 h ECG recordings in the University of Virginia Holter database. We found dynamical phenotypes for the three rhythm classifications. As expected, AF records had the highest variability and entropy, and NSR the lowest. SR with ectopy could be distinguished from AF, which had higher entropy, and from NSR, which had different fractal scaling, measured as higher detrended fluctuation analysis slope. With these dynamical phenotypes, we developed successful classification strategies, and the nonlinear measures improved on the use of mean and variability alone, even after adjusting for age. Final models using all variables had excellent performance, with positive predictive values for AF, NSR and SR with ectopy as high as 97, 98 and 90%, respectively. Since these classifiers can reliably detect rhythm changes utilizing segments as short as 10 min, we envision their application in noisy settings and in personal monitoring devices where only RR interval time series may be available.