The molecular structure of E-cadherin and its function are intimately related to β-catenin, their interactions ensuring the cell morphology and stability. Alterations of E-cadherin-β-catenin complex facilitate the tumor growth and spreading in the carcinogenic mechanism. We aimed to assess the E-cadherin and β-catenin immunoexpressions in different variants of papillary thyroid carcinoma (PTC), and the relationship of these markers with the clinicopathological prognostic factors. Our study group included 70 cases of PTC divided into two risk groups. The low-risk group comprised 45 cases diagnosed as conventional, follicular, oncocytic, macrofollicular, and clear cell variants, whereas the high-risk group consisted of 25 cases diagnosed as tall cell, follicular angioinvasive, cribriform-morular, hobnail, diffuse sclerosing, and solid subtype, respectively. Immunohistochemical exam was performed by using anti-E-cadherin and anti-β-catenin antibodies, and their expressions were semi-quantitatively evaluated. The association between E-cadherin and β-catenin, respectively, and clinicopathological prognostic factors was statistically analyzed. We noted statistically significant differences between membranous E-cadherin expression (low versus high) and tumor size, histological risk groups, tumor stage, lymph node metastases, vascular invasion and tumor relapse. We also found statistically significant correlation between membranous β-catenin expression (low versus high) and the risk groups, tumor size and tumor stage, but no associations of cytoplasmic β-catenin (low versus high) with the clinicopathological characteristics. Our study demonstrates that E-cadherin and β-catenin expressions differ in low- and high-risk groups of PTC. The aggressive behavior of the high-risk histological variants is associated with reduced membranous E-cadherin, and loss of membranous β-catenin followed by enhanced cytoplasmic expression. These results open large standpoints for a deeper characterization of the histological variants of PTC.