Multimedia information, typically image information, is growing rapidly across the Internet and elsewhere. To keep pace with the increasing volumes of image information, new techniques need to be investigated to retrieve images intelligently and efficiently. Content-based image retrieval (CBIR) is always a challenging task. In this chapter, a stochastic mechanism, called Markov Model Mediator (MMM), is used to facilitate the searching and retrieval process for content-based image retrieval, which serves as the retrieval engine of the CBIR systems and uses stochastic-based similarity measures. Different from the common methods, our stochastic mechanism carries out the searching and similarity computing process dynamically, taking into consideration not only the image content features but also other characteristics of images such as their access frequencies and access patterns. Our experimental results demonstrate that the MMM mechanism together with the stochastic process can assist in retrieving more accurate results for user queries.