While online social networks (OSNs) have become an important platform for information exchange, the abuse of OSNs to spread misinformation has become a significant threat to our society. To restrain the propagation of misinformation in its early stages, we study the Distance-constrained Misinformation Combat under Uncertainty problem, which aims to both reduce the spread of misinformation and enhance the spread of correct information within a given propagation distance. The problem formulation considers the competitive diffusion of misinformation and correct information. It also accounts for the uncertainty in identifying initial misinformation adopters. For competitive propagation with major-threshold activation, we propose a solution based on stochastic programming and provide an upper-bound in the presence of uncertainty. We propose an efficient Combat Seed Selection algorithm to tackle general-threshold activation, in which we define a measure, “effectiveness”, to evaluate the contribution of nodes to the fight against misinformation. Through extensive experiments, we validate that our algorithm outputs high-quality solution with very fast computation.