Nontypeable Haemophilus influenzae (NTHi) is a leading causative organism of opportunistic respiratory tract infections. However, there are currently no effective vaccination strategies, and existing treatments are compromised by antibiotic resistance. We previously characterized Haemophilus haemolyticus (Hh) strains capable of producing haemophilin (HPL), a heme-binding protein that restricts NTHi growth by limiting its access to an essential growth factor, heme. Thus, these strains may have utility as a probiotic therapy against NTHi infection by limiting colonization, migration and subsequent infection in susceptible individuals. Here, we assess the preliminary feasibility of this approach by direct in vitro competition assays between NTHi and Hh strains with varying capacity to produce HPL. Subsequent changes in NTHi growth rate and fitness, in conjunction with HPL expression analysis, were employed to assess the NTHi-inhibitory capacity of Hh strains. HPL-producing strains of Hh not only outcompeted NTHi during short-term and extended co-culture, but also demonstrated a growth advantage compared with Hh strains unable to produce the protein. Additionally, HPL expression levels during competition correlated with the NTHi-inhibitory phenotype. HPL-producing strains of Hh demonstrate significant probiotic potential against NTHi colonization in the upper respiratory tract, however, further investigations are warranted to demonstrate a range of other characteristics that would support the eventual development of a probiotic.