Discrete response of structures often is a key probabilistic quantity of interest. For example, one may need to identify the probability of a binary event, such as whether a structure has buckled. This study used an adaptive domain-based decomposition and classification method, combined with sparse grid sampling, to develop an efficient classification surrogate modeling algorithm for such discrete outputs. An assumption of monotonic behavior of the output with respect to all model parameters, based on the physics of the problem, helps to reduce the number of model evaluations and makes the algorithm more efficient. As an application problem, this paper developed a computational framework for generation of a probabilistic penetration response of S-2 glass/SC-15 epoxy composite plates under ballistic impact. This enables the computationally feasible generation of the probabilistic velocity response (PVR) curve, or the V-0-V-100 curve, as a function of the impact velocity, and prediction of the ballistic limit velocity as a function of the model parameters. The PVR curve incorporates the variability of the model input parameters and describes the probability of penetration of the plate as a function of impact velocity. (C) 2021 American Society of Civil Engineers.