Most studies of diabetic polyneuropathy (DPN) and painful DPN are conducted in persons with longstanding diabetes. This cross-sectional study aimed to estimate the prevalence of DPN and painful DPN, important risk factors, and the association with mental health in recently diagnosed type 2 diabetes. A total of 5,514 (82%) patients (median diabetes duration 4.6 years) enrolled in the Danish Centre for Strategic Research in Type 2 Diabetes cohort responded to a detailed questionnaire on neuropathy and pain. A score ≥ 4 on the MNSI questionnaire determined possible DPN whereas pain presence in both feet together with a score ≥ 3 on the DN4 questionnaire determined possible painful DPN. The prevalence of possible DPN and possible painful DPN was 18% and 10%, respectively. Female sex, age, diabetes duration, BMI, and smoking were associated with possible DPN, whereas only smoking showed a clear association with possible painful DPN (OR 1.52 [95% CI: 1.20; 1.93]). Possible DPN and painful DPN were independently and additively associated with lower quality-of-life, poorer sleep, and symptoms of depression and anxiety. Possible DPN itself had greater impact on mental health than neuropathic pain. This large study emphasizes the importance of careful screening for DPN and pain early in the course of type 2 diabetes.