Background: Tracheostomy is performed in ventilated stroke patients affected by persisting severe dysphagia, reduced level of consciousness, or prolonged mechanical ventilation. The study aim was to determine the frequency and predictors of successful decannulation and long-term functional outcome in tracheotomized stroke patients. Methods: A prospective single-center observational study recruited ventilated patients with ischemic stroke, intracerebral hemorrhage, and subarachnoid hemorrhage. Follow-up visits were performed at hospital discharge, 3, and 12 months. Competing risk analyses were performed to identify predictors of decannulation. Results: We included 53 ventilated stroke patients who had tracheostomy. One year after tracheostomy, 19 patients were decannulated (median [IQR] time to decannulation 74 [58–117] days), 13 patients were permanently cannulated, and 21 patients died without prior removal of the cannula. Independent predictors for decannulation in our cohort were patient age (HR 0.95 [95% CI: 0.92–0.99] per one year increase, p = 0.003) and absence of sepsis (HR 4.44 [95% CI: 1.33–14.80], p = 0.008). Compared to surviving patients without cannula removal, decannulated patients had an improved functional outcome after one year (median modified Rankin Scale score 4 vs. 5 [p < 0.001]; median Barthel index 35 vs. 5 [p < 0.001]). Conclusions: Decannulation was achieved in 59.4% of stroke patients surviving the first 12 months after tracheostomy and was associated with better functional outcome compared to patients without decannulation. Further prospective studies with larger sample sizes are needed to confirm our results.