We describe a new variable selection procedure for categorical responses where the candidate models are all probit regression models. The procedure uses objective intrinsic priors for the model parameters, which do not depend on tuning parameters, and ranks the models for the different subsets of covariates according to their model posterior probabilities. When the number of covariates is moderate or large, the number of potential models can be very large, and for those cases, we derive a new stochastic search algorithm that explores the potential sets of models driven by their model posterior probabilities. The algorithm allows the user to control the dimension of the candidate models and thus can handle situations when the number of covariates exceed the number of observations. We assess, through simulations, the performance of the procedure and apply the variable selector to a gene expression data set, where the response is whether a patient exhibits pneumonia. Software needed to run the procedures is available in the R package varselectIP. Copyright © 2011 John Wiley & Sons, Ltd.