Phenotypic evolution may occur either through alterations to the structure of protein-coding genes or their expression. Evidence for which of these two mechanisms more commonly contribute to the evolution of a phenotype can be garnered from examples of parallel and convergent evolution. The visual system of East African cichlid fishes is an excellent system with which to address this question. Cichlid fishes from Lakes Malawi (LM) and Victoria together exhibit three diverse palettes of coexpressed opsins and several important protein-coding mutations that both shift spectral sensitivity. Here we assess both opsin expression and protein-coding diversity among cichlids from a third rift lake, Lake Tanganyika (LT). We found that Tanganyikan cichlids exhibit three palettes of coexpressed opsins that largely overlap the short-, middle-, and long-wavelength-sensitive palettes of LM cichlids. Bayesian phenotypic clustering and ancestral state reconstructions both support the parallel evolution of the short- and middle-wavelength palettes among cichlids from LT and LM. In each case, these transitions occurred from different ancestors that expressed the same long-wavelength palette. We also identified similar but distinct patterns of correlated evolution between opsin expression, diet, and lens transmittance among cichlids from LT and LM as well. In contrast to regulatory changes, we identified few functional or potentially functional mutations in the protein-coding sequences of three variable opsins, with the possible exception of the SWS1 (ultraviolet) opsin. These results underscore the important contribution that gene regulation can make to rapid phenotypic evolution and adaptation.