The evaluation of the alternatives against multiple criteria is of the utmost importance in a multi-criteria decision making (MCDM) problem. It is often the case that the experts have a varying degree of confidence in their evaluations. That is, an evaluation has an associated degree of credibility. To take into account this crucial piece of information in determining the best choice, we present a new data structure. More specifically, we present a confidence-based soft set. We also extend the same to the fuzzy and intuitionistic fuzzy domains. The proposed concepts are elucidated through a number of illustrative examples. We establish their usefulness in a real case-study.