Macrophages are critical players in regulating innate and adaptive immunity in the tumor microenvironment (TME). The prognostic value of macrophages and their heterogeneous phenotypes in non-small cell lung cancer (NSCLC) is still uncertain. Surgically-resected samples of 681 NSCLC cases were stained by multiplex immunofluorescence to examine macrophage phenotypes as well as the expression levels of program death-ligand 1 (PD-L1) on them in both tumor nest and tumor stroma, including pan-macrophage (CD68+), M1 (CD68+CD163-), and M2 macrophages (CD68+CD163+). Various other immune cell markers, including CD4, CD8, CD20, CD38, CD66B, FOXP3, and CD133, were also evaluated. Machine learning algorithm by Random Forest (RF) model was utilized to screen the robust prognostic markers and construct the CD68-based immune-related risk score (IRRS) for predicting disease-free survival (DFS). The expression levels of CD68 were moderately correlated with the levels of PD-L1 (P<0.001), CD133 (P<0.001), and CD8 (P<0.001). Higher levels of CD68 (OR 1.03, 95% CI: 1.01-1.05, P<0.001) as well as M1 macrophage (OR 1.04, 95% CI: 1.01-1.06, P<0.001) indicated shorter DFS. Despite without statiscial significance, intratumoral M2 macrophage (OR 1.05, 95% CI: 0.99-1.10, P=0.081) was also associated with worse DFS. IRRS incorporating three intratumoral CD68-related markers and four intrastromal markers was constructed and validated to predict recurrence (high-risk group vs. low-risk group: OR 2.52, 95% CI: 1.89-3.38, P<0.001). The IRRS model showed good accuracy [area under the curve (AUC) =0.670, 0.709, 0.695, 0.718 for 1-, 3-, 5-year, and overall DFS survival, respectively] and the predictive performance was better than the single-marker model (area under the curve 0.718 vs. 0.500-0.654). A nomogram based on clinical characteristics and IRRS for relapse prediction was then established and exhibited better performance than the tumor-node-metastasis (TNM) classification and IRRS system (C-index 0.76 vs. 0.69 vs. 0.60, 0.74 vs. 0.67 vs. 0.60, 0.81 vs. 0.74 vs. 0.60 of the entire, training, testing cohort, respectively). Our study suggested close interactions between CD68 and other immune markers in TME, demonstrating the prognostic value of CD68 in relapse prediction in resectable NSCLC.