Multiple-Instance Learning (MIL) represents a new class of supervised learning tasks, where training examples are bags of instances with labels only available for the bags. To solve the instance label ambiguity, instance selection based MIL models were proposed to convert bag learning to traditional vector learning. However, existing MIL instance selection approaches are all based on the instances inside the bags. In this case, at the original instance space, those potential informative instances, which do not occur in the bags are discarded. In this paper, we propose a novel learning method, MILEIS (Multiple-Instance Learning with Evolutionary Instance Selection), to adaptively determine the informative instances for feature mapping. The unique evolutionary search mechanism, including instance initialization, mutation, and crossover, ensures that MILEIS can adjust itself to the data without explicit specification of functional or distributional form for the underlying model. By doing so, MILEIS can also take full advantage of those creative informative instances to help feature mapping in an accurate way. Experiments and comparisons on real-world applications demonstrate the effectiveness of the proposed method.