Herb recommendation aims to recommend a set of herbs based on the patients’ symptoms. Although the existing graph representation learning methods obtain promising performance for herb recommendation, the interactions between the symptoms and herbs in the real world are far beyond the pairwise correlation, which cannot be effectively modeled by the general bipartite graph. In this paper, we propose a new solution called Heterogeneous Hypergraph Polynomial Learning (HPPL). First, we construct the heterogeneous hypergraph according to the rich structures and attributes. The heterogeneous hyperedges can better model the complex correlations than the general graphs. Second, we develop a polynomial learning framework to replace the Laplacian decomposition, making our model more efficient. The empirical results show that our proposed model significantly outperforms the state-of-the-art methods. Moreover, we also show that our model is more efficient than the general hypergraphs.