Paroxysmal Atrial Fibrillation (PAF) is a very common heart disease caused by irregular impulses of atrial tissue in adult. Diagnosing in the early stages of this disorder is very important for the patients to stop the progression of the disease and to improve the life quality. In this study, it is aimed to predict the PAF event before the realization of the PAF which in 5 minutes for the PAF patients. 30-minute data used in the study were divided into 5-minute parts. Fast Fourier Transform of frequency domain measures of heart rate variability obtained easily and practically is used for each part. The statistical significances among segments and discriminating performances of k-Nearest Neighbors classifier were obtained for each segment using these measurements. Consequently, As a result of statistical analysis, it is shown that patients may be warned 12.5 minutes earlier than a PAF attack.