Paroxysmal atrial fibrillation (Paro. AF) is challenging to identify at the right moment. This disease is often undiagnosed using currently existing methods. Nonlinear analysis is gaining importance due to its capability to provide more insight into complex heart dynamics. The aim of this study is to use several recently developed nonlinear techniques to discriminate persistent AF (Pers. AF) from normal sinus rhythm (NSR), and more importantly, Paro. AF from NSR, using short-term single-lead electrocardiogram (ECG) signals. Specifically, we adapted and modified the time-delayed embedding method to minimize incorrect embedding parameter selection and further support to reconstruct proper phase plots of NSR and AF heart dynamics, from MIT-BIH databases. We also examine information-based methods, such as multiscale entropy (MSE) and kurtosis (Kt) for the same purposes. Our results demonstrate that embedding parameter time delay (τ), as well as MSE and Kt values can be successfully used to discriminate between Pers. AF and NSR. Moreover, we demonstrate that τ and Kt can successfully discriminate Paro. AF from NSR. Our results suggest that nonlinear time-delayed embedding method and information-based methods provide robust discriminating features to distinguish both Pers. AF and Paro. AF from NSR, thus offering effective treatment before suffering chaotic Pers. AF.