Initial microbial colonization and later succession in the gut of human infants are linked to health and disease later in life. The timing of the appearance of the first gut microbiome, and the consequences for the early life metabolome, are just starting to be defined. Here, we evaluated the gut microbiome, proteome and metabolome in 88 African-American newborns using faecal samples collected in the first few days of life. Gut bacteria became detectable using molecular methods by 16 h after birth. Detailed analysis of the three most common species, Escherichia coli, Enterococcus faecalis and Bacteroides vulgatus, did not suggest a genomic signature for neonatal gut colonization. The appearance of bacteria was associated with reduced abundance of approximately 50 human proteins, decreased levels of free amino acids and an increase in products of bacterial fermentation, including acetate and succinate. Using flux balance modelling and in vitro experiments, we provide evidence that fermentation of amino acids provides a mechanism for the initial growth of E. coli, the most common early colonizer, under anaerobic conditions. These results provide a deep characterization of the first microbes in the human gut and show how the biochemical environment is altered by their appearance.