(1) Background: The role of cytoreductive nephrectomy (CN) is controversial in patients with primary metastatic renal cell carcinoma (mRCC). (2) Methods: We evaluated the impact of CN, or no CN, followed by first-line targeted therapy (TT) in a nationwide unselected cohort of 437 consecutive patients with primary mRCC over a two-year period with a minimum of five years of follow-up. Data sources were national registries supplemented with manually extracted information from individual patient medical records. Cox proportional hazards estimated the hazard ratio (HR) of overall death and cancer-specific death after one and three years. (3) Results: 210 patients underwent CN and 227 did not. A total of 176 patients (40%) had CN followed by TT, 160 (37%) had TT alone, 34 (8%) underwent CN followed by observation, and 67 (15%) received no treatment. After adjustments in Model 2, patients treated with TT alone demonstrated a worsened overall survival (OS) compared to those treated with CN + TT, HR 0.63 (95% CI: 0.19–2.04). (4) Conclusions: In this nationwide study, CN was associated with enhanced outcomes in carefully selected patients with primary mRCC. Further randomized trials are warranted.