Cytoglobin is a heme protein with unresolved physiological function. Genetic deletion of zebrafish cytoglobin (cygb2) causes developmental defects in left-right cardiac determination, which in humans is associated with defects in ciliary function and low airway epithelial nitric oxide production. Here we show that Cygb2 co-localizes with cilia and with the nitric oxide synthase Nos2b in the zebrafish Kupffer’s vesicle, and that cilia structure and function are disrupted in cygb2 mutants. Abnormal ciliary function and organ laterality defects are phenocopied by depletion of nos2b and of gucy1a, the soluble guanylate cyclase homolog in fish. The defects are rescued by exposing cygb2 mutant embryos to a nitric oxide donor or a soluble guanylate cyclase stimulator, or with over-expression of nos2b. Cytoglobin knockout mice also show impaired airway epithelial cilia structure and reduced nitric oxide levels. Altogether, our data suggest that cytoglobin is a positive regulator of a signaling axis composed of nitric oxide synthase–soluble guanylate cyclase–cyclic GMP that is necessary for normal cilia motility and left-right patterning.