Alfalfa (Medicago sativa) is the most widely grown and most important forage crop in the world. However, alfalfa is susceptible to waterlogging stress, which is the major constraint for its cultivation area and crop production. So far, the molecular mechanism of alfalfa response to the waterlogging is largely unknown. Here, comparative transcriptome combined with proteomic analyses of two cultivars (M12, tolerant; M25, sensitive) of alfalfa showing contrasting tolerance to waterlogging were performed to understand the mechanism of alfalfa in response to waterlogging stress. Totally, 748 (581 up- and 167 down-regulated) genes were differentially expressed in leaves of waterlogging-stressed alfalfa compared with the control (M12_W vs. M12_CK), whereas 1193 (740 up- and 453 down-regulated) differentially abundant transcripts (DATs) were detected in the leaves of waterlogging-stressed plants in comparison with the control plants (M25_W vs. M25_CK). Furthermore, a total of 187 (122 up- and 65 down-regulated) and 190 (105 up- and 85 down-regulated) differentially abundant proteins (DAPs) were identified via isobaric tags for relative and absolute quantification (iTRAQ) method in M12_W vs. M12_CK and M25_W vs. M25_CK comparison, respectively. Compared dataset analysis of proteomics and transcriptomics revealed that 27 and eight genes displayed jointly up-regulated or down-regulated expression profiles at both mRNA and protein levels in M12_W vs. M12_CK comparison, whereas 30 and 27 genes were found to be co-up-regulated or co-down-regulated in M25_W vs. M25_CK comparison, respectively. The strongly enriched Kyoto Encyclopedia of Genes and Genomes (KEGG) pathways for co-up-regulated genes at mRNA and protein levels in M12_W vs. M12_CK comparison were 'Amino sugar and nucleotide sugar metabolism', 'Arginine and proline metabolism' and 'Starch and sucrose metabolism', whereas co-up-regulated protein-related pathways including 'Arginine and proline metabolism' and 'Valine, leucine and isoleucine degradation' were largely enriched in M25_W vs. M25_CK comparison. Importantly, the identified genes related to beta-amylase, Ethylene response Factor (ERF), Calcineurin B-like (CBL) interacting protein kinases (CIPKs), Glutathione peroxidase (GPX), and Glutathione-S-transferase (GST) may play key roles in conferring alfalfa tolerance to waterlogging stress. The present study may contribute to our understanding the molecular mechanism underlying the responses of alfalfa to waterlogging stress, and also provide important clues for further study and in-depth characterization of waterlogging-resistance breeding candidate genes in alfalfa.