Amaranths (Amaranthus sp.) are a popular leafy vegetable grown and consumed by resource-poor people in many African countries. Greater awareness of the importance of nutritious foods has increased demand by African consumers for amaranth. Presently, most African farmers grow low-yielding local varieties of variable seed quality. High-yielding amaranth varieties that are adapted to the major agro-ecologies of eastern and southern Africa possess key traits needed by male and female farmers and meet diverse market preferences are required. The objective of this study was to identify amaranth lines adapted to major amaranth production environments in Kenya and Tanzania using a gender-disaggregated farmers participatory approach to explore possible gender differences in trait and variety preferences. Twenty amaranth entries were evaluated for vegetable yield, agronomic traits, and organoleptic taste tests in replicated, farmer-participatory variety selection trials at one location in Kenya and at four locations in Tanzania. Differences among entries (G), locations (E), and G × E interaction were significant or highly significant for marketable vegetable yield. Location followed by entry was the most important factor that explained differences in yield. G and G × E interaction biplot analysis classified the five locations into two different mega-environments, mainly based on altitude, temperatures, and soil characteristics. Marketable vegetable yield was positively correlated with leaf length, plant height, and the selection scores of female and male farmers at almost all locations. Selection scores of female and male farmers were positively correlated, indicating that male and female farmers shared similar amaranth variety preferences. Farmers identified and ranked important traits that can be used by breeders to design amaranth product profiles and develop amaranth breeding objectives. Lines combining high yield with high farmer and consumer preference scores have been retained for distinctiveness, uniformity, and stability tests for possible release as commercial varieties.