Core promoters are crucial regions for initiation of gene transcription. Identification of core promoters is important to the understanding of transcriptional regulation and elucidation of relationships among genes of an organism. Experimentally locating core promoters is laborious and costly. Therefore, it is desirable to develop computational approaches to support and complement experimental methods. However, computational prediction of core promoters of eukaryotic species is challenging. In this paper, we first formulate the core promoter prediction problem as a variation of the multiple instance learning problem. We then develop a new algorithm for identifying core promoters with a high positive prediction rate and a high sensitivity. Since many computational biology problems can be formulated under the multiple instance learning paradigm, our approach may inspire future research of applying multiple instance learning techniques to complex biology problems and our method may have broad potential applications.