Background: Emergency medical services (EMS) are the first health care contact for the majority of stroke patients. However, there is a lack of data on the current paramedics’ hospital-directed feedback and training needs across different health care settings. We aimed to evaluate paramedics’ prehospital stroke care knowledge, training needs, and current status of feedback on suspected stroke patients. Methods: We surveyed paramedics from the Vilnius region from September to November 2019 and compared the answers between the city and the district agencies. The questionnaire content included questions on paramedics’ demographic characteristics, prehospital stroke care self-assessment, knowledge on stroke mimics, stroke training needs, and the importance of hospital-directed feedback on suspected stroke patients. Results: A total number of 161 paramedics (or 49.4% of all paramedics from our stroke care network) were surveyed, with more district paramedics rating their prehospital stroke care knowledge as inadequate (44.8% (95% confidence interval (CI) 32.8−57.6) vs. 28.1% (95% CI 20.1−27.8), p = 0.028). In addition, more district paramedics indicated a need for additional stroke training (83.1% (95% CI 71.5−90.5) vs. 69.8% (60.0−78.1), p = 0.043). However, respondents reported being the most confident while dealing with stroke (71.3%, 95% CI 63.8−77.7) compared to other time-critical conditions (p < 0.001). Vertigo (60.8%, 95% CI 53.0−68.0), brain tumors (56.3%, 95% CI 48.5−63.8), and seizures (54.4%, 95% CI 46.7−62.0) were indicated as the most common stroke mimics. Only 6.2% (95% CI 3.4−11.1) of respondents received formal feedback on the outcome of suspected stroke patients brought to the emergency department. Conclusions: A high proportion of paramedics self-perceive having inadequate stroke knowledge and an urgent need for further stroke training. The EMS staff indicate receiving insufficient feedback on suspected stroke patients, even though its usefulness is perceived as paramount.