Cross-feeding, a relationship wherein one organism consumes metabolites excreted by another, is a ubiquitous feature of natural and clinically-relevant microbial communities and could be a key factor promoting diversity in extreme and/or nutrient-poor environments. However, it remains unclear how readily cross-feeding interactions form, and therefore our ability to predict their emergence is limited. In this paper we developed a mathematical model parameterized using data from the biochemistry and ecology of an E. coli cross-feeding laboratory system. The model accurately captures short-term dynamics of the two competitors that have been observed empirically and we use it to systematically explore the stability of cross-feeding interactions for a range of environmental conditions. We find that our simple system can display complex dynamics including multi-stable behavior separated by a critical point. Therefore whether cross-feeding interactions form depends on the complex interplay between density and frequency of the competitors as well as on the concentration of resources in the environment. Moreover, we find that subtly different environmental conditions can lead to dramatically different results regarding the establishment of cross-feeding, which could explain the apparently unpredictable between-population differences in experimental outcomes. We argue that mathematical models are essential tools for disentangling the complexities of cross-feeding interactions.