Background: In humans, methane (CH4) is exclusively produced by the intestinal microbiota and has been implicated in several conditions including cardiovascular disease. After microbial production of CH4 in the gut, it steadily crosses into the systemic circulation and reaches the lungs where it can be detected in the exhaled breath, as a surrogate measure for intestinal CH4 production. Recent reports have shown an association between CH4 and vagal dysfunction as well as the inhibition of CH4 activity on ileal contractions with atropine, suggesting its action on the parasympathetic nervous system. Given these findings, we hypothesized that CH4 may be affecting resting heart rate (HR) based on the potential effect of CH4 on the vagus nerve. Objectives: Given its possible role in the parasympathetic nervous system, we aimed to study the relationship between breath CH4 and resting HR in humans. Additionally, we performed a longitudinal study analyzing the change in HR and its association with breath CH4 over time. Methods: First, we reviewed 1,126 subjects and compared HR in subjects with detectable and undetectable breath CH4. Second, we performed a post hoc analysis of a randomized control trial to compare the change in HR for those who had an increase in breath CH4 versus those that had a decrease in breath CH4 over 14 weeks. Last, we assessed whether a larger decrease in CH4 is associated with a larger increase in HR over time. Results: In the retrospective cohort, subjects with detectable CH4 had a lower HR compared to those with undetectable CH4 (73.0 ± 0.83 vs. 76.0 ± 0.44 beats/min, p = 0.01). In the post hoc analysis, a decrease in CH4 over time was associated with an increase in HR (median ∆ = 6.5 ± 8.32 beats/min, p = 0.0006). Last, we demonstrated a biological gradient whereby a larger drop in CH4 was associated with a greater increase in HR (R = −0.31, p = 0.03). Conclusion: Our findings suggest a potential role for the microbiome (and specifically CH4 from methanogens) to regulate HR. Considering these findings, mechanistic studies are warranted to further investigate this potential novel microbiome-neurocardiac axis.