Higher-order representation is suitable for the complicated relationships among many factors. However, existing higher-order classification models have difficulties in learning from high-dimensional data due to their large combinatorial hypothesis spaces. The interpretability of models is also significant for causality analysis. Here we propose a Bayesian evolutionary method to learn a higher-order graphical model for high-dimensional data, called Bayesian evolutionary hypernetwork (BEHN). Our method represents the combinatorial feature space using a generalized graph, hypernetwork. A hypernetwork contains a large population of hyperedges encoding higher-order relationships among feature variables, and is optimized by an evolutionary algorithm formulated as sequential Bayesian sampling. This Bayesian evolutionary approach allows for probabilistic search through the higher-order feature space while satisfying soft constraints defined by the priors. We show that two information-theoretic and complexity-related priors are effective to balance model accuracy and parsimony. Also, BEHN provides interpretable representations to investigate feature interactions. Using two benchmarking and three real-world datasets we demonstrate that BEHN outperforms baseline classification models while tackling large-scale data of dimensionality up to O(104). We also analyze the stability and the scalability of the proposed method with respect to accuracy, computational cost, and the interpretability of the model structures.