Molybdenum (Mo) is essential for the biological assimilation of inorganic nitrogen (N). We compared Mo requirements for N2‐fixation in two species of filamentous heterocystous cyanobacteria (HC) to test the hypothesis that coastal HC require higher Mo concentrations than freshwater HC. This expectation follows from the fact that Mo is more concentrated in seawater (~ 105 nmol L−1) than in most freshwaters (< 20 nmol L−1). Contrary to this hypothesis, we found that both strains maintained N2‐fixation for 30 d at 10 nmol L−1. Mo concentrations < 1 nmol L−1 induced N‐limitation in both species, as indicated by increased C:N ratios and decreased nitrogenase expression and activity. This response took time to induce, likely due to high‐affinity molybdate uptake by both species. Measurable N2‐fixation persisted in the coastal strain (Nostoc sp. CCMP 2511) for at most 12 d; 3 d were required for chlorophyll a concentrations to fall below those of Mo‐replete cultures. An additional 7 d and 11 d, respectively, were required for N2‐fixation rates and chlorophyll levels to decline in Mo‐limited freshwater cultures (Nostoc sp. PCC 7120). When Mo was high (> 1 µmol L−1), the freshwater strain exhibited considerable Mo storage (> 100 µmol mol−1 Mo: C) whereas cellular Mo remained < 10 µmol mol−1 Mo:C in the coastal strain. The high Mo content and extended time required for N2‐fixation to decrease in the freshwater strain could be due to expression of the gene mop, which encodes a putative molybdate‐storage protein. This study suggests the importance of Mo storage in freshwater HC.