Segmentation of the vertebrate hindbrain into rhombomeres is a key step in the development of a complex pattern of differentiated neurons from a homogeneous neuroepithelium. Many of the transcription factors important for establishing the segmental plan and assigning rhombomere identity are now known. However, the downstream effectors that bring about the formation of rhombomere boundaries are only just being characterized. Here we discuss molecules that could be responsible for segregating populations of cells from different rhombomeres. We focus on recent work demonstrating that the Eph family of receptor tyrosine kinases and their ligands, the ephrins, function in rhombomere-specific cell sorting and initiation of a structural boundary. We discuss the contributions of two mechanisms -- cell sorting and plasticity -- to the formation of rhombomere boundaries.