Objective: Headache prevalence among children and adolescents has increased over the last few years. Evidence-based treatment options for pediatric headaches remain limited. Research suggests a positive influence of odors on pain and mood. We investigated the effect of repeated exposure to odors on pain perception, headache-related disability, and olfactory function in children and adolescents with primary headaches. Methods: Eighty patients with migraine or tension-type headache (mean 13.1 ± 3.29 years) participated, of whom 40 underwent daily olfactory training with individually selected pleasant odors for 3 months and 40 received state-of-the-art outpatient therapy as a control group. At baseline and after a 3-month follow-up, olfactory function [odor threshold; odor discrimination; odor identification; comprehensive Threshold, Discrimination, Identification (TDI) score], mechanical detection and pain threshold (quantitative sensory testing), electrical pain threshold, patient-reported outcomes on headache-related disability [Pediatric Migraine Disability Assessment (PedMIDAS)], pain disability [Pediatric Pain Disability Index (P-PDI)], and headache frequency were assessed. Results: Training with odors significantly increased the electrical pain threshold compared to the control group (U = 470.000; z = −3.177; p = 0.001). Additionally, olfactory training significantly increased the olfactory function (TDI score [t(39) = −2.851; p = 0.007], in particular, olfactory threshold, compared to controls (U = 530.500; z = −2.647; p = 0.008). Headache frequency, PedMIDAS, and P-PDI decreased significantly in both groups without a group difference. Conclusions: Exposure to odors has a positive effect on olfactory function and pain threshold in children and adolescents with primary headaches. Increased electrical pain thresholds might reduce sensitization for pain in patients with frequent headaches. The additional favorable effect on headache disability without relevant side effects underlines the potential of olfactory training as valuable nonpharmacological therapy in pediatric headaches.