High-calorie diets lead to hepatic steatosis and to the development of non-alcoholic fatty liver disease (NAFLD), which can evolve over many years into the inflammatory form of non-alcoholic steatohepatitis (NASH), posing a risk for the development of hepatocellular carcinoma (HCC). Due to diet and liver alteration, the axis between liver and gut is disturbed, resulting in gut microbiome alterations. Consequently, detecting these gut microbiome alterations represents a promising strategy for early NASH and HCC detection. We analyzed medical parameters and the fecal metaproteome of 19 healthy controls, 32 NASH patients, and 29 HCC patients, targeting the discovery of diagnostic biomarkers. Here, NASH and HCC resulted in increased inflammation status and shifts within the composition of the gut microbiome. An increased abundance of kielin/chordin, E3 ubiquitin ligase, and nucleophosmin 1 represented valuable fecal biomarkers, indicating disease-related changes in the liver. Although a single biomarker failed to separate NASH and HCC, machine learning-based classification algorithms provided an 86% accuracy in distinguishing between controls, NASH, and HCC. Fecal metaproteomics enables early detection of NASH and HCC by providing single biomarkers and machine learning-based metaprotein panels.