(1) Background: Headache disorders are among the most disabling medical conditions but the supply with experienced providers is outpaced by the demand for service. It is unclear to what extent particularly patients in rural regions are affected by limited access to comprehensive care. Furthermore, it is unknown what role general practitioners (GPs) play in headache care. (2) Methods: First-time consultations to a specialised headache clinic at a tertiary care centre were asked to participate. Their socio-demographic background, general and headache-specific medical history, disability and quality of life (QoL) were assessed. Additionally, 176 GPs in neighbouring districts were contacted regarding headache management. (3) Results: We assessed 162 patients with first-time consultations (age 46.1 ± 17.0 years, 78.1% female), who suffered from migraine (72%), tension type, cluster and secondary headaches (each 5-10%). About 50% of patients received a new headache-diagnosis and 60% had treatment inconsistent with national guidelines. QoL was significantly worse in all domains compared to the general population. About 75% of GPs see headache patients at least several times per week, and mostly treat them by themself. (4) Conclusions: More than every second headache patient was neither correctly diagnosed nor received guideline adherent treatment. Headache-related disability is inferior to what is expected from previous studies. Access to specialised health care is more limited in rural than in urban regions in Germany and GPs request more training.