Some cyanobacteria can generate hydrogen (H2) under certain physiological conditions and are considered potential agents for biohydrogen production. However, they also present low amounts of H2 production, a reaction reversal towards H2 consumption, and O2 sensitivity. Most attempts to improve H2 production have involved genetic or metabolic engineering approaches. I used a bio-prospecting approach instead to find novel strains that are naturally more apt for biohydrogen production. A set of 36, phylogenetically diverse strains isolated from terrestrial, freshwater and marine environments were probed for their potential to produce H2 from excess reductant. Two distinct patterns in H2 production were detected. Strains displaying Pattern 1, as previously known from Synechocystis sp. PCC 6803, produced H2 only temporarily, reverting to H2 consumption within a short time and after reaching only moderately high H2 concentrations. By contrast, Pattern 2 cyanobacteria, in the genera Lyngbya and Microcoleus, displayed high production rates, did not reverse the direction of the reaction and reached much higher steady-state H2 concentrations. L. aestuarii BL J, an isolate from marine intertidal mats, had the fastest production rates and reached the highest steady-state concentrations, 15-fold higher than that observed in Synechocystis sp. PCC 6803. Because all Pattern 2 strains originated in intertidal microbial mats that become anoxic in dark, it was hypothesized that their strong hydrogenogenic capacity may have evolved to aid in fermentation of the photosynthate. When forced to ferment, these cyanobacteria display similarly desirable characteristics of physiological H2 production. Again, L. aestuarii BL J had the fastest specific rates and attained the highest H2 concentrations during fermentation, which proceeded via a mixed-acid pathway to yield acetate, ethanol, lactate, H2, CO2 and pyruvate. The genome of L. aestuarii BL J was sequenced and bioinformatically compared to other cyanobacterial genomes to ascertain any potential genetic or structural basis for powerful H2 production. The association hcp exclusively in Pattern 2 strains suggests its possible role in increased H2 production. This study demonstrates the value of bioprospecting approaches to biotechnology, pointing to the strain L. aestuarii BL J as a source of useful genetic information or as a potential platform for biohydrogen production.