© 2014 IEEE. Hidden Markov models (HMMs) have previously been successfully applied to subsurface threat detection using ground penetrating radar (GPR) data. However, parameter estimation in most HMM-based landmine detection approaches is difficult since object locations are typically well known for the 2-D coordinates on the Earth's surface but are not well known for object depths underneath the ground/time of arrival in a GPR A-scan. As a result, in a standard expectation maximization HMM (EM-HMM), all depths corresponding to a particular alarm location may be labeled as target sequences although the characteristics of data from different depths are substantially different. In this paper, an alternate HMM approach is developed using a multiple-instance learning (MIL) framework that considers an unordered set of HMM sequences at a particular alarm location, where the set of sequences is defined as positive if at least one of the sequences is a target sequence; otherwise, the set is defined as negative. Using the MIL framework, a collection of these sets (bags), along with their labels is used to train the target and nontarget HMMs simultaneously. The model parameters are inferred using variational Bayes, making the model tractable and computationally efficient. Experimental results on two synthetic and two landmine data sets show that the proposed approach performs better than a standard EM-HMM.