Millettia speciosa Champ (MSP) is a natural Chinese herb that improves gastrointestinal health and enhances animal immunity. An 8-week feeding trial with different MSP levels (0, 150, 300, and 600 mg/kg) was conducted to evaluate the promotive effects of MSP in Cyprinus carpio. Results indicate that MSP improved intestinal immunity to some extent evidenced by the immuno-antioxidant parameters and the 16S rRNA in the Illumina MiSeq platform. With the analysis of transcriptome sequencing, 4685 differentially expressed genes (DEGs) were identified, including 2149 up-regulated and 2536 down-regulated. According to the GO and KEGG enrichments, DEGs were mainly involved in the immune system. Transcriptional expression of the NOD-like signaling pathway and key genes retrieved from the transcriptome database confirmed that innate immunity was improved in response to dietary MSP administration. Therefore, MSP could be used as a feed supplement that enhances immunity. This may provide insight into Chinese herb additive application in aquaculture production.