We report an idealized numerical study of a melting and freezing solid adjacent to a turbulent, buoyancy-affected shear flow, in order to improve our understanding of topography generation by phase changes in the environment. We use the phase-field method to dynamically couple the heat equation for the solid with the Navier–Stokes equations for the fluid. We investigate the evolution of an initially flat and horizontal solid boundary overlying a pressure-driven turbulent flow. We assume a linear equation of state for the fluid and change the sign of the thermal expansion coefficient, such that the background density stratification is either stable, neutral or unstable. We find that channels aligned with the direction of the mean flow are generated spontaneously by phase changes at the fluid–solid interface. Streamwise vortices in the fluid, the interface topography and the temperature field in the solid influence each other and adjust until a statistical steady state is obtained. The crest-to-trough amplitude of the channels is larger than approximately 10 the viscous length scale, but is much larger and more persistent for an unstable stratification than for a neutral or stable stratification. This happens because a stable stratification makes the cool melt fluid buoyant such that it shields the channel from further melting, whereas an unstable stratification makes the cool melt fluid sink, inducing further melting by rising hot plumes. The statistics of flow velocities and melt rates are investigated, and we find that channels and keels emerging in our simulations do not significantly change the mean drag coefficient.