Objective: The aim of our study was to assess the prevalence and characteristics of nutritional risk in patients scheduled for cardiovascular rehabilitation. Background: Knowledge concerning nutritional aspects of cardiovascular diseases is contemporary limited. Methods: Nutritional risk screening using a standardized Nutritional Risk Screening–2002 (NRS-2002) questionnaire was performed on a cohort of consecutive patients scheduled for rehabilitation 1–6 months after treatment for ischemic, valvular, or combined causes of heart diseases. Baseline weight was available for more than 80% of patients. Results: The study population consisted of 317 patients, aged 23–85 years, with a mean age of 62.5 ± 11.3 years. Male to female share was 253 (79.8%) and 64 (20.2%), respectively. Twenty-eight (8.8%) were treated for myocardial infarction conservatively, 151 (47.6%) by percutaneous coronary interventions, and 145 (45.7%) by surgery. NRS-2002 was 3.56 ± 1.54 in range 0–6. A high correlation was found between the NRS-2002 and percentage weight loss history (rho = 0.813; p < 0.001), disease etiology (p = 0.002), cardiovascular treatments (p < 0.001), and grades of renal function (p < 0.001). Odds for developing increased nutritional risk (NRS-2002 ≥ 3) were significant for cardiovascular treatments (odds ratio [OR] = 4.35, 95% confidence interval [CI], 2.28–8.30, p < 0.001), age (OR = 3.19, 95% CI, 2.00–5.09, p < 0.001), grade of renal function (OR = 1.91, 95% CI, 1.17–3.09, p = 0.009), diabetes mellitus (OR = 2.37, 95% CI, 1.09–5.16, p = 0.029), and any psychological disturbance (OR = 2.04, 95% CI, 1.06–3.90, p = 0.032). Conclusions: Pronounced nutritional risk frequently existed among patients at stationary cardiovascular rehabilitation. Nutritional risk was connected with preceding cardiovascular treatments, patient age, and renal function. Further studies concerning nutritional risk and its connections with clinical outcomes might serve as a resourceful perspective to improve outcomes or quality of care for the entities from the cardiovascular diseases continuum.