Entamoeba histolytica, the protozoan responsible for human amoebiasis, causes between 30,000 and 100,000 deaths per year worldwide. Amoebiasis is characterized by intestinal epithelial damage provoking severe diarrhea. However, the molecular mechanisms by which this protozoan causes epithelial damage are poorly understood. Here, we studied the initial molecular interactions between the E. histolytica EhCPADH112 virulence complex and epithelial MDCK and Caco-2 cells. By confocal microscopy, we discovered that after contact with trophozoites or trophozoite extracts (TE), EhCPADH112 and proteins forming this complex (EhCP112 and EhADH112) co-localize with occludin and claudin-1 at tight junctions (TJ). Immunoprecipitation assays revealed interaction between EhCPADH112 and occludin, claudin-1, ZO-1 and ZO-2. Overlay assays confirmed an interaction of EhCP112 and EhADH112 with occludin and claudin-1, whereas only EhADH112 interacted also with ZO-2. We observed degradation of all mentioned TJ proteins after incubation with TE. Importantly, inhibiting proteolytic activity or blocking the complex with a specific antibody not only prevented TJ protein degradation but also epithelial barrier disruption. Furthermore, we discovered that TE treatment induces autophagy and apoptosis in MDCK cells that could contribute to the observed barrier disruption. Our results suggest a model in which epithelial damage caused by E. histolytica is initiated by the interaction of EhCP112 and EhADH112 with TJ proteins followed by their degradation. Disruption of TJs then induces increased paracellular permeability, thus facilitating the entry of more proteases and other parasite molecules leading eventually to tissue destruction.