Exercise necessitates a large supply of O₂ and nutrients and rapid removal of CO₂ and waste products. Histamine is a regulator of the microcirculation (which performs these exchanges), suggesting a possible involvement of histamine in exercise. Histamine is released from either mast cells or non-mast cells. In the latter, histamine is newly formed via the induction of histidine decarboxylase (HDC) in response to an appropriate stimulus, and it is released without being stored. Here, in mice, we examined the role of histamine or HDC induction in exercise. Prolonged walking (PW) (in a cylindrical cage turned electrically) increased HDC mRNA and HDC activity in quadriceps femoris muscles. Mice given a histamine H1-receptor antagonist [fexofenadine (peripherally acting) or pyrilamine (peripherally and centrally acting)] or an irreversible HDC inhibitor (α-fluoromethylhistidine) displayed less PW endurance than control mice. Ranitidine (H2-receptor antagonist) tended to reduce endurance. Other histamine-receptor (H3 and H4) antagonists had no significant effects on endurance. Mice deficient in HDC or histamine H1-receptors displayed markedly less endurance than control mice, and HDC activity in the quadriceps femoris of H1-deficient mice was rapidly elevated by PW. Fexofenadine significantly reduced the muscle levels of nitric oxide (NO) metabolites and glycogen after PW. The results support the ideas that (i) histamine is involved in protecting against exercise-induced fatigue or exhaustion, (ii) histamine exerts its protective effect via H1 receptors and the ensuing production of NO in skeletal muscle, and (iii) histamine is provided, at least in part, by HDC induction in skeletal muscles during prolonged exercise.