Non-homogeneous processes and, in particular, base compositional non-stationarity have long been recognized as a critical source of systematic error. But only a small fraction of current molecular systematic studies methodically examine and effectively account for the potentially confounding effect of non-stationarity. The problem is especially overlooked in multi-locus or phylogenomic scale analyses, in part because no efficient tools exist to accommodate base composition heterogeneity in large data sets. We present a detailed analysis of a data set with 20 genes and 214 taxa to study the phylogeny of flatfishes (Pleuronectiformes) and their position among percomorphs. Most genes vary significantly in base composition among taxa and fail to resolve flatfish monophyly and other emblematic groups, suggesting that non-stationarity may be causing systematic error. We show a strong association between base compositional bias and topological discordance among individual gene partitions and their inferred trees. Phylogenetic methods applying non-homogeneous models to accommodate non-stationarity have relatively minor effect to reduce gene tree discordance, suggesting that available computer programs applying these methods do not scale up efficiently to the data set of modest size analysed in this study. By comparing phylogenetic trees obtained with species tree (STAR) and concatenation approaches, we show that gene tree discordance in our data set is most likely due to base compositional biases than to incomplete lineage sorting. Multi-locus analyses suggest that the combined phylogenetic signal from all loci in a concatenated data set overcomes systematic biases induced by non-stationarity at each partition. Finally, relationships among flatfishes and their relatives are discussed in the light of these results. We find support for the monophyly of flatfishes and confirm findings from previous molecular phylogenetic studies suggesting their close affinity with several carangimorph groups (i.e., jack and allies, barracuda, archerfish, billfish and swordfish, threadfin, moonfish, beach salmon, and snook and barramundi).