Cellulose degradation by anaerobic bacteria plays an eminent role in the global carbon cycle and is a critical step in biofuel production. The anaerobe thermophile Clostridium thermocellum (now: Acetivibrio thermocellus) is particularly efficient at breaking down biomass and produces a 'yellow affinity substance' (YAS), a pigment that has been implicated in signaling and conferring a higher affinity of the cellulosome to YAS-loaded cellulose. However, despite its importance, the nature and biosynthetic origin of YAS have remained elusive. Here we show by isolation and structure elucidation that YAS is a complex of unusual arylpolyene alkaloids (celluxanthenes). Stable isotope labeling experiments reveal all biosynthetic building blocks for celluxanthene assembly. Through a targeted gene deletion, we identify the celluxanthene (cex) biosynthesis gene cluster and propose a biosynthetic model in which an arylpolyene generated by an iterative type I polyketide synthase (PKS) undergoes a head-to-head fusion with a tryptophan-derived ketoacid to form a tetronate. Genome mining and metabolic profiling revealed that diverse cellulolytic anaerobes harbor cex gene loci and produce celluxanthene congeners. Celluxanthenes show antibiotic activity against Gram-positive bacteria. This study work solves the long-standing enigma surrounding the nature of YAS, establishes bioengineering approaches, and helps elucidating the biological roles of these intricate pigments.