Abstract: Increasing efforts are directed towards the development of sustainable alternative protein sources among which microbial protein (MP) is one of the most promising. Especially when waste streams are used as substrates, the case for MP could become environmentally favorable. The risks of using organic waste streams for MP production–the presence of pathogens or toxicants–can be mitigated by their anaerobic digestion and subsequent aerobic assimilation of the (filter-sterilized) biogas. Even though methane and hydrogen oxidizing bacteria (MOB and HOB) have been intensively studied for MP production, the potential benefits of their co-cultivation remain elusive. Here, we isolated a diverse group of novel HOB (that were capable of autotrophic metabolism), and co-cultured them with a defined set of MOB, which could be grown on a mixture of biogas and H2/O2. The combination of MOB and HOB, apart from the CH4 and CO2 contained in biogas, can also enable the valorization of the CO2 that results from the oxidation of methane by the MOB. Different MOB and HOB combinations were grown in serum vials to identify the best-performing ones. We observed synergistic effects on growth for several combinations, and in all combinations a co-culture consisting out of both HOB and MOB could be maintained during five days of cultivation. Relative to the axenic growth, five out of the ten co-cultures exhibited 1.1–3.8 times higher protein concentration and two combinations presented 2.4–6.1 times higher essential amino acid content. The MP produced in this study generally contained lower amounts of the essential amino acids histidine, lysine and threonine, compared to tofu and fishmeal. The most promising combination in terms of protein concentration and essential amino acid profile was Methyloparacoccus murrelli LMG 27482 with Cupriavidus necator LMG 1201. Microbial protein from M. murrelli and C. necator requires 27–67% less quantity than chicken, whole egg and tofu, while it only requires 15% more quantity than the amino acid-dense soybean to cover the needs of an average adult. In conclusion, while limitations still exist, the co-cultivation of MOB and HOB creates an alternative route for MP production leveraging safe and sustainably-produced gaseous substrates.