ABSTRACT Fasciclins (FAS1) are ancient adhesion protein domains found across different phyla from bacteria to humans, with no common small ligand binding function reported. A unique FAS1-containing astaxanthin-binding protein (AstaP) from green algae can efficiently bind an unusually broad repertoire of carotenoids (astaxanthin, zeaxanthin, canthaxanthin, β-carotene), but the underlying mechanism is largely unknown. Here we dissect the structural basis for the ligand binding promiscuity of AstaP-orange1 (AstaPo1) by determining its solution NMR structure in complex with its natural ligand, astaxanthin (AXT), and validate this structure by SAXS, calorimetry, optical spectroscopy and mutagenesis data. While the unstructured tails of AstaPo1 are not essential for carotenoid binding, they enhance protein solubility. The a1-a2 helices of the AstaPo1 FAS1 domain embrace the carotenoid polyene like a jaw, organizing a conserved hydrophobic tunnel, too short to prevent the AXT β-ionone rings from protruding on both sides of the tunnel, thereby not imposing specificity restrictions. The only specific protein-AXT interactions involve H-bonds between the oxygenated groups on AXT and a peripheral Gln56 residue. Remarkably, mapping of this and other AXT-contacting AstaPo1 residues revealed their different conservation in AstaP orthologs with the tentative carotenoid-binding function and in FAS1 proteins in general, supporting neofunctionalization of AstaPs within green algae. Correspondingly, a cyanobacterial homolog with a similar domain structure cannot bind carotenoids due to subtle differences in residues decorating the tunnel. These structure-activity relationships inform the sequence-based prediction of the carotenoid-binding FAS1 members. SIGNIFICANCE A water-soluble astaxanthin-binding protein (AstaP) is a photoprotective protein in green algae helping them to tolerate stress conditions. While belonging to a ubiquitous protein family sharing an ancient structural domain, fasciclin, involved in cell adhesion, AstaP possesses an outstanding ability to bind carotenoid pigments of a different type, which are potent antioxidants. To understand the molecular basis for such carotenoid-binding promiscuity of AstaP, here we determined its spatial structure – the first structure of a carotenoid-protein complex solved by nuclear magnetic resonance spectroscopy. Together with biochemical and sequence conservation analyses, our data illustrate a remarkable case of neofunctionalization of the ancient protein domain and pave the way for its bioengineering and practical use as antioxidant transporter for biomedical applications.