Search engines are the major instruments on the Web. The determination of the liability of the results returned by a typical search engine is a daunting challenge mainly due to the presence of Web spams. New types of Web spams are continuously introduced every now and then, which makes it drastically challenging to decide about the accuracy of the results. The problem looks like a reasoning problem in the presence of uncertainty. This paper presents a methodology for predicting Web spam where the spamicity of hosts is formulated as a reasoning problem. The approach is based on evidence theory, a mathematical prediction model based on Dempster-Shafer Theory (DST). The key benefit of our approach for Web spam is DST's ability to deal with the uncertainty. When a new spam is introduced in the system, the system lacks a reasonable prior knowledge. This is where DST provides more liable solution to detect spams without any prior information. The paper presents detailed statistical evaluations of the proposed approach where an accuracy of 99.27% in detecting Web spams is reported.