Among major cereals domesticated as staple food, only sorghum has a high proportion of cultivars with condensed tannins in grain, which can trigger bitter taste perception in animals by binding to type 2 taste receptors (TAS2Rs). Here, we report the completion of uncovering of a pair of duplicate recessive genes (Tannin1 and Tannin2) underlying tannin presence. Three loss-of-function alleles from each gene were identified in non-tannin sorghum desired as palatable food. Condensed tannins effectively prevented sparrows from consuming sorghum grain. Parallel geographic distributions between tannin sorghum and Quelea quelea supported the role of tannins in fighting against this major herbivore threat. Association between geographic distributions of human TAS2R variants and tannin sorghum across Africa suggested that different causes had probably driven this bidirectional selection according to varied local herbivore threats and human taste sensitivity. Our investigation uncovered coevolution among humans, plants and environments linked by allelochemicals.