Positive feedback driven by transcriptional regulation has long been considered a key mechanism underlying cell lineage segregation during embryogenesis. Using the developing spinal cord as a paradigm, we found that canonical, transcription-driven feedback cannot explain robust lineage segregation of motor neuron subtypes marked by two cardinal factors, Hoxa5 and Hoxc8. We propose a feedback mechanism involving elementary microRNA-mRNA reaction circuits that differ from known feedback loop-like structures. Strikingly, we show that a wide range of biologically plausible post-transcriptional regulatory parameters are sufficient to generate bistable switches, a hallmark of positive feedback. Through mathematical analysis, we explain intuitively the hidden source of this feedback. Using embryonic stem cell differentiation and mouse genetics, we corroborate that microRNA-mRNA circuits govern tissue boundaries and hysteresis upon motor neuron differentiation with respect to transient morphogen signals. Our findings reveal a previously underappreciated feedback mechanism that may have widespread functions in cell fate decisions and tissue patterning.