Summary: We consider the number and distribution of minima in random landscapes defined on non-Euclidean lattices. Using an ensemble where random landscapes are reweighted by a fugacity factor z for each minimum that they contain, we construct first a ‘two-box’ mean field theory. This exhibits an ordering phase transition at \(z_c = 2\) above which one box contains an extensive number of minima. The onset of order is governed by an unusual order parameter exponent \({\beta} = 1\), motivating us to study the same model on the Bethe lattice. Here we find from an exact solution that for any connectivity \({\mu}+1>2\) there is an ordering transition with a conventional mean field order parameter exponent \({\beta} = 1/2\), but with the region where this behaviour is observable shrinking in size as \(1/{\mu}\) in the mean field limit of large \({\mu}\). We show that the behaviour in the transition region can also be understood directly within a mean field approach, by making the assignment of minima ‘soft’. Finally we demonstrate, in the simplest mean field case, how the analysis can be generalized to include both maxima and minima. In this case an additional first-order phase transition appears, to a landscape in which essentially all sites are either minima or maxima.