Waterlogging is one of the major abiotic stresses that affects barley production and yield quality. Proteomics techniques have been widely utilized to explore the mechanisms involved in the responses to abiotic stress. In this study, two barley genotypes with contrasting responses to waterlogging stress were analyzed with proteomic technology. The waterlogging treatment caused a greater reduction in biomass and photosynthetic performance in the waterlogging-sensitive genotype TF57 than that in the waterlogging-tolerant genotype TF58. Under waterlogging stress, 30, 30, 20 and 20 differentially expressed proteins were identified through tandem mass spectrometry analysis in the leaves, adventitious roots, nodal roots and seminal roots, respectively. Among these proteins, photosynthesis-, metabolism- and energy-related proteins were differentially expressed in the leaves, with oxygen-evolving enhancer protein 1, ATP synthase subunit and heat shock protein 70 being up-regulated in TF58. Pyruvate decarboxylase (PDC), 1-amino cyclopropane 1-carboxylic acid oxidase (ACO), glutamine synthetase (GS), glutathione S-transferases (GST) and beta-1, 3-glucanase in adventitious, nodal and seminal roots were more abundant in TF58 than those in TF57 under waterlogging stress. Ten representative genes were selected for validation by qRT-PCR in different genotypes with known waterlogging tolerance, and the expression levels of three candidate genes (PDC, ACO and GST) increased in the roots of all genotypes in response to the waterlogging stress. These three genes might play a significant role in the adaptation process of barley under waterlogging stress. The current results partially determined the mechanisms of waterlogging tolerance and provided valuable information for the breeding of barley with enhanced tolerance to waterlogging.