Inguinal lymph node surgery is a standard treatment for penile cancer patients with intermediate or high risk for lymph node metastasis (LNM) according to European Association of Urology (EAU) risk grading. We are proposing a more objective histological prognostic grading system for inguinal LNM in these patients. We assessed worst pattern of invasion, lymphocytic host response, lymphovascular invasion, and perineural invasion in a population-based cohort of 306 penile cancer patients. Patients were classified into low, intermediate, and high risk for inguinal LNM. There was a significant association both between risk groups and pT stage (p < 0.001) and between risk groups and LNM. Univariate logistic regression showed 25.43 times higher odds of LNM for patients in the intermediate risk group compared with the low risk group (odds ratio (OR) 25.43; 95% confidence interval (CI): 5.94-108.97) and a 177.13 times higher odds in the high risk group compared to the low risk group (OR 177.13; 95% CI: 40.09-782.51). When comparing our histological risk grading with the EAU grading, we found a higher sensitivity, of 51.28% (95% CI: 45.68-56.88) versus 37.09% (95% CI: 31.68-42.50), as well as a higher area under the curve (0.86; 95% CI: 0.81-0.89; versus 0.65; 95% CI: 0.58-0.71) with our grading system. While our grading classified 111 patients as low risk, only 31 were considered low risk for LNM according to the EAU risk classification. The new histological risk grading system shows a higher sensitivity and includes a higher number of patients in the low risk group in whom lymph node surgery could be avoided, reducing morbidity and costs.