The local invasiveness and occasional rapid growth of chordomas, despite optimal treatment, highlight the need to develop ways to predict their biologic behavior. Alterations in adhesion proteins have been shown to participate in proliferation, invasiveness, and metastasis in epithelial tumors. We therefore analyzed the expression of E-cadherin, N-cadherin, as well as their cytosolic binding proteins alpha-catenin, beta-catenin, and gamma-catenin, in 51 paraffin archived and 17 cryopreserved chordoma specimens. In the majority of chordomas, E-cadherin and N-cadherin expression was inversely correlated, whereas beta-catenin and gamma-catenin expression was directly correlated. By multivariate analysis, N-cadherin up-regulation correlated with a diminished recurrence-free survival, and E-cadherin down-regulation strongly correlated with increased probabilities of death as determined by the Kaplan-Meier log-rank test. There was a 3.28-fold increased probability of having a tumor recurrence and a 10.98-fold increased probability of dying when, respectively, N-cadherin was up-regulated and E-cadherin down-regulated. These results suggest that changes in the relative expression of the cadherin-catenin complex reflect chordoma aggressiveness; and that decreased expression of E-cadherin and increased expression of N-cadherin may underlie the transition from a less to a more aggressive tumor phenotype.