Non-typeable Haemophilus influenzae (NTHi) is an important cause of human respiratory tract infections, particularly in the young, the old, and indigenous populations. Efforts to treat and prevent NTHi infections have been hampered by antibiotic resistance and difficulties in finding a suitable vaccine target. Alternative treatment or prevention strategies are therefore desired. The bacterium Haemophilus haemolyticus is closely related to NTHi, occupies the same niche and is non-pathogenic. These characteristics, along with production of a substance inhibitory to NTHi, would make H. haemolyticus suited as a respiratory probiotic to counter NTHi infection. We screened culture broth extracts from 100 isolates of Haemophilus haemolyticus for production of substances inhibitory to NTHi, using a well diffusion assay. One isolate of H. haemolyticus consistently produced a substance that inhibited all tested NTHi. The substance was proteinaceous and resistant to denaturation by heat, acid and basic conditions. We purified the inhibitory substance by size exclusion chromatography, and determined the primary structure of a candidate protein by mass spectrometry of a trypsin digest. The amino acid sequence of the protein was determined by database matching of the peptide against translated published whole genomes. Using qPCR assays and Sanger sequencing we were able to show that the gene was present in 15 of the 100 H. haemolyticus isolates, and that 6, including the initial producer strain, had an identical sequence. We cloned the gene into E. coli DH5 alpha then expressed it with E. coli BL21. The resulting recombinant protein inhibited NTHi. Our results show that some isolates of H. haemolyticus do produce a novel protein that is inhibitory to NTHi, and that further research for the development of H. haemolyticus as a probiotic inhibitory to NTHi is warranted.