Paroxysmal atrial fibrillation (PAF) is a cardiac arrhythmia that can eventually lead to heart failure or stroke if left untreated. Early detection of PAF is therefore crucial to prevent any further complications and avoid fatalities. An implantable defibrillator device could be used to both detect and treat the condition though such devices have limited computational capability. With this constraint in mind, this paper presents a novel set of features to accurately predict the presence of PAF. The method is evaluated using ECG signals from the widely used atrial fibrillation prediction database (AFPDB) from PhysioNet. We analysed 106 signals from 53 pairs of ECG recordings. Each pair of signals contains one 5-min ECG segment that ends just before the onset of a PAF event and another 5-min ECG segment at least 45 min distant from the PAF event, to represent a non-PAF event. Seven novel features are extracted through the Poincare representation of R-R interval signals, and are prioritised through feature ranking schemes. The features are used with four standard classification techniques for PAF prediction and compared to the existing state of the art from the literature. Using only the seven proposed features, classification performance outperforms those of the classical state-of-the-art feature set, registering sensitivity and specificity measurements of over 96%. The results further improve when the features are combined with several of the classical features, with an accuracy increasing to 98% using a linear kernel SVM. The results show that the proposed features provide a useful representation of the PAF condition and achieve good prediction with off-the-shelf classification techniques that would be suitable for ICU deployment.