China uses a multilevel agricultural certification system; however, its implications are not well understood. In this study, we used tomatoes as an example in a series of Becker-DeGroot-Marschak auction experiments to determine consumers’ willingness to pay (WTP) toward three safety certification labels and two kinds of brands. Then, based on the auction experiment results, we designed a menu-based choice experiment to assess the interaction relationships between the safety certification labels and brands. The results showed that consumers were generally willing to pay a premium for tomatoes with safety-certified labels (especially for organic labels) and brands (especially for the enterprise brand). Providing consumers with additional information regarding the certification remarkably improved their WTP for tomatoes with organic and green labels. The menu-based choice experiment suggested that the organic and green labels were found to be substitutes. In addition, organic and green labels could not substitute the enterprise brand, whereas the converse of this relationship was true. Finally, a mutual substitution relationship was observed between hazard-free label and enterprise brand. Our research enables producers to consider the interaction between certification strategies and brand strategies. Therefore, marketers and policymakers should take steps to promote and expand consumers’ knowledge on certification, as it could benefit the development of certified food.