Lineage-specific regulation of tumor progression by the same transcription factor is understudied. We find that levels of the FOXQ1 transcription factor, an oncogene in carcinomas, are decreased during melanoma progression. Moreover, in contrast to carcinomas, FOXQ1 suppresses epithelial-to-mesenchymal transition, invasion, and metastasis in melanoma cells. We find that these lineage-specific functions of FOXQ1 largely depend on its ability to activate (in carcinomas) or repress (in melanoma) transcription of the N-cadherin gene (CDH2). We demonstrate that FOXQ1 interacts with nuclear β-catenin and TLE proteins, and the β-catenin/TLE ratio, which is higher in carcinoma than melanoma cells, determines the effect of FOXQ1 on CDH2 transcription. Accordingly, other FOXQ1-dependent phenotypes can be manipulated by altering nuclear β-catenin or TLE proteins levels. Our data identify FOXQ1 as a melanoma suppressor and establish a mechanism underlying its inverse lineage-specific transcriptional regulation of transformed phenotypes.