This study aimed to develop an interpretable prognostic model with a nomogram for Non-Small Cell Lung Cancer (NSCLC) recurrence prediction following complete resection, using multi-modality PET/CT fusion radiomics and patients' clinical features. Retrospectively, 181 NSCLC patients who had undergone18F-FDG PET/CT scan were enrolled and split into training (2/3) and testing (1/3) partitions. Before image fusion, PET and CT images were registered, resized to equal isotropic voxel size, and clipped and normalized. Guided Filtering Fusion GFF algorithm was used for image fusion. Two hundred eighteen radiomic features were extracted from each PET, CT, and fused image, including morphological, first-order statistical, and texture features. Clinical features included age, sex, smoking status, weight, radiation, chemotherapy, pathological stage, etc. Feature selection and univariate and multivariate modeling were performed using the CoxBoost algorithm. Harrell's Concordance index (C-index) was used to evaluate the performance of the models, and compare C test was used to statistically compare the performance of the models (p-values < 0.05 were considered significant). Clinical, Clinical+PET, Clinical+CT, and Clinical+GFF resulted in c-indices (confidence interval) of 0.701 (0.589-0.812), 0.757 (0.647-0.867), 0.706 (0.607, 0.807), and 0.824 (0.751-0.896), respectively. Statistical comparison of the performance of different models with the Clinical model revealed that while PET and GFF features can significantly increase the performance (p-values 0.009 and 0.001, respectively), CT features did not significantly improve the performance of the Clinical model (p-value 0.279). Therefore, the nomogram was developed based on the Clinical+GFF model (with the best performance). Radiomic features extracted from PET and PET/CT fusion images can improve the recurrence prognosis in NSCLC patients compared to the conventional clinical factors alone.