Knowledge that stroke patients have concomitant coronary artery disease (CAD) is crucial for neurological rehabilitation, because the disease affects the long-term morbidity and mortality of the patients. This knowledge may influence the choice of pharmacological and neurorehabilitation therapies. However, due to the lack of standard routine screening, CAD positive stroke patients often remain unidentified. In this cross-sectional prospective, single-center study we tested a non-invasive screening approach for CAD, employing extracranial color-coded Duplex ultrasound (ECCS) and an oscillatory measurement of arterial stiffness. Overall, significant CAD was tested using bicycle stress electrocardiography (BSE). Patients who had experienced their first stroke but had no history of CAD were examined while in neurological rehabilitation after successful early mobilization. We measured both common carotid arteries to determine intima-media thickness (IMT), presence and extent of plaque, and pulsatility (PI) and resistance (RI) indices. Arterial stiffness was measured using peripheral arterial tonometry (PAT). Of 100 patients (mean/median ages 61/59.2 years; 69 male) in the study, only 14 proved physically able to undergo BSE, and in only 6 patients was ST elevation observed on the baseline electrocardiogram. The IMT was highly correlated with changes in vessel elasticity (RI, PI, and PAT finding) but not with pathological BSE findings, which identified ST elevation in only one patient. Carotid ECCS results correlate with PAT measurements of arterial stiffness, indicating generalized atherosclerosis. Neither method could predict the presence of significant CAD. However, BSE is not the gold standard for CAD detection. Pathological ECG changes were found in fewer patients than expected, indicating a lower risk of CAD than previously reported for other similar patient groups.