Despite an increasing awareness of the potential of "orphan" or unimproved crops to contribute to food security and enhanced livelihoods for farmers, coordinated research agendas to facilitate production and use of orphan crops by local communities are generally lacking. We provide an overview of the current knowledge on leafy vegetables with a focus on Gynandropsis gynandra, a highly nutritious species used in Africa and Asia, and highlight general and species-specific guidelines for participatory, genomics-assisted breeding of orphan crops. Key steps in genome-enabled orphan leafy vegetables improvement are identified and discussed in the context of Gynandropsis gynandra breeding, including: (1) germplasm collection and management; (2) product target definition and refinement; (3) characterization of the genetic control of key traits; (4) design of the 'process' for cultivar development; (5) integration of genomic data to optimize that 'process'; (6) multi-environmental participatory testing and end-user evaluation; and (7) crop value chain development. The review discusses each step in detail, with emphasis on improving leaf yield, phytonutrient content, organoleptic quality, resistance to biotic and abiotic stresses and post-harvest management.