Atrial fibrillation (AF) is the most common arrhythmia that causes stroke. The paroxysmal atrial fibrillation (PAF) is a type of AF that is self-terminated in less than 7 days and can recur later. This paper proposed new markers from electrocardiogram (ECG) for PAF prediction. The heart rate variability (HRV) obtained from ECG was use in this investigation. The Shannon entropy (ENT) and amplitude variation (VAR) were derived from the wavelet temporal information in different frequency band of HRV. The K-nearest neighbor classifier was employed to discriminate the wavelet markers between normal group and PAF group. The wavelet markers in low frequency band (LF: 0.04-0.15 Hz) and high frequency (HF: 0.15-0.4 Hz) are significantly different between normal group and PAF group. The best performance is obtained from the classifier with K = 7 achieved 71±1.5% sensitivity and 65±1.4%specificity.