Incipient valley formation in mountainous landscapes is often associated with their presence at a regular spacing under diverse hydroclimatic forcings. Here we provide a formal linear stability theory for a landscape evolution model (LEM) representing the action of tectonic uplift, diffusive soil creep, and detachment-limited fluvial erosion. For configurations dominated by only one horizontal length scale, a single dimensionless quantity characterizes the overall system dynamics based on model parameters and boundary conditions. The stability analysis is conducted for smooth and symmetric hillslopes along a long mountain ridge to study the impact of the erosion law form on regular first-order valley formation. The results provide the critical condition when smooth landscapes become unstable and give rise to a characteristic length scale for incipient valleys, which is related to the scaling exponents that couple fluvial erosion to the specific drainage area and the local slope. The valley spacing at first instability is uniquely related to the ratio of the scaling exponents and expands logarithmically with an increase in this ratio. We find compelling evidence of sediment transport by diffusive creep and fluvial erosion coupled with the specific drainage area equation as a sufficient mechanism for first-order valley formation. We finally show that the predictions of the linear stability analysis conform with the results of numerical simulations for different degrees of nonlinearity in the erosion law and agree well with topographic data from a natural landscape.