Background: Headache is a frequent symptom following COVID-19 immunization with a typical onset within days post-vaccination. Cases of cerebral venous thrombosis (CVT) have been reported in adenovirus vector-based COVID-19 vaccine recipients. Findings: We reviewed all vaccine related CVT published cases by April 30, 2021. We assessed demographic, clinical variables and the interval between the vaccination and onset of headache. We assessed whether the presence of headache was associated with higher probability of death or intracranial hemorrhage. We identified 77 cases of CVT after COVID-19 vaccination. Patients’ age was below 60 years in 74/77 (95.8%) cases and 61/68 (89.7%) were women. Headache was described in 38/77 (49.4%) cases, and in 35/38 (92.1%) was associated with other symptoms. Multiple organ thrombosis was reported in 19/77 (24.7%) cases, intracranial hemorrhage in 33/77 (42.9%) cases and 19/77 (24.7%) patients died. The median time between vaccination and CVT-related headache onset was 8 (interquartile range 7.0–9.7) days. The presence of headache was associated with a higher odd of intracranial hemorrhage (OR 7.4; 95% CI: 2.7–20.8, p < 0.001), but not with death (OR: 0.51, 95% CI: 0.18–1.47, p = 0.213). Conclusion: Delayed onset of headache following an adenovirus vector-based COVID-19 vaccine is associated with development of CVT. Patients with new-onset headache, 1 week after vaccination with an adenovirus vector-based vaccine, should receive a thorough clinical evaluation and CVT must be ruled out.