Variable selection is a vital problem in expert systems and in knowledge discovery. However, traditional variable selection methods achieve low accuracies on large and complex datasets because they do not consider the importance of variable combinations. A variable combination is a variable set in which the combined variables fit better than do other, redundant variables, but each of which, considered individually, may fit worse. Therefore, an association-based evolutionary ensemble variable selection method for multiple linear regression is proposed. Both greedy algorithms and stochastic algorithms are applied under an ensemble framework. Instead of ranking variables according to selection frequency, the associations among variables in local solutions are considered to identify important variable combinations. Experiments show that the proposed approach has a competitive performance for variable selection and outperforms some classic methods on large-scale datasets. The study is important for automated feature discovery for complex systems with multiple combined input variables.