Many quality signals—both private and public—have been used to foster the development of food quality in the agro-food markets: mainly brands and common certified labels. Previous research has typically focused on either brand or certified label efficiency independently, while in many instances both signals coexist. Agricultural products that pair brand names and certified labels—such as indications of origin—are indeed common: e.g., Roquefort cheese, Scotch whiskeys, and most of the French wines. The objective of our paper is to take into account this coexistence by empirically analyzing the complementarity and/or substitutability that may exist between labels and brands. To do so, we estimate different models of adoption and an original multinomial probit model of complementarity that we test on a database of the quality-signaling strategies from 993 small French cooperatives. Our main result shows that there is a clear interaction effect between brand and certified label signal strategies, but it is a substitution effect rather than a complementary one.