The emergence and rapid dissemination of antibiotic resistance, worldwide, threatens medical progress and calls for innovative approaches for the management of multidrug resistant infections. Phage-therapy, i.e., the use of viruses (phages) that specifically infect and kill bacteria during their life cycle, is a re-emerging and promising alternative to solve this problem. The success of phage therapy mainly relies on the exact matching between the target pathogenic bacteria and the therapeutic phage. Currently, there are only a few tools or methodologies that efficiently predict phage-bacteria interactions suitable for the phage therapy, and the pairs phage-bacterium are thus empirically tested in laboratory. In this paper we present an original methodology, based on an ensemble-learning approach, to predict whether or not a given pair of phage-bacteria would interact. Using publicly available information from Genbank and phagesdb. org, we assembled a dataset containing more than two thousand phage-bacterium interactions with their corresponding genomes. A set of informative features, extracted from these genomes, form the base of the quantitative datasets used to train our predictive models. These features include the distribution of predicted protein-protein interaction scores, as well as the amino acid frequency, the chemical composition, and the molecular weight of such proteins. Using an independent test dataset to evaluate the performance of our methodology, our approach gets encouraging performance with more than 90% of accuracy, specificity, and sensitivity.