Divergent natural selection acting in different habitats may build up barriers to gene flow and initiate speciation. This speciation continuum can range from weak or no divergence to strong genetic differentiation between populations. Here, we focus on the early phases of adaptive divergence in the East African cichlid fish Astatotilapia burtoni, which occurs in both Lake Tanganyika (LT) and inflowing rivers. We first assessed the population structure and morphological differences in A. burtoni from southern LT. We then focused on four lake-stream systems and quantified body shape, ecologically relevant traits (gill raker and lower pharyngeal jaw) as well as stomach contents. Our study revealed the presence of several divergent lake-stream populations that rest at different stages of the speciation continuum, but show the same morphological and ecological trajectories along the lake-stream gradient. Lake fish have higher bodies, a more superior mouth position, longer gill rakers and more slender pharyngeal jaws, and they show a plant/algae and zooplankton-biased diet, whereas stream fish feed more on snails, insects and plant seeds. A test for reproductive isolation between closely related lake and stream populations did not detect population-assortative mating. Analyses of F1 offspring reared under common garden conditions indicate that the detected differences in body shape and gill raker length do not constitute pure plastic responses to different environmental conditions, but also have a genetic basis. Taken together, the A. burtoni lake-stream system constitutes a new model to study the factors that enhance and constrain progress towards speciation in cichlid fishes.