There are today several methods and standards available for assessment of the level of information security in an enterprise. A problem with these assessment methods is that they neither provide an indication of the amount of effort required to obtain the assessment nor an approximation of this measure?s credibility. This paper describes a part of a new method for assessing the level of enterprise information security expresses the credibility of the results in terms of confidence levels and make use of an estimation of the cost of searching for security evidence. Such methods for predicting information search cost of assessments are detailed in the paper. Search cost predictions are used for providing guidance on how to minimize the effort spent on performing enterprise information security assessments. The conclusions are based on a security assessment performed at a large European energy company and a statistical survey among Swedish security experts.