In this paper, we consider the task of discovering the common objects in images. Initially, object candidates are generated in each image and an undirected weighted graph is constructed over all the candidates. Each candidate serves as a node in the graph while the weight of the edge describes the similarity between the corresponding pair of candidates. The problem is then expressed as a search for the Maximum Weight Clique (MWC) in this graph. The MWC corresponds to a set of object candidates sharing maximal mutual similarity, and each node in the MWC represents a discovered common object across the images. Since the problem of finding the MWC is NP-hard, most research of the MWC problem focuses on developing various heuristics for finding good cliques within a reasonable time limit. We utilize a recently very popular class of heuristics called local search methods. They search for the MWC directly in the discrete domain of the solution space. The proposed approach is evaluated on the PASCAL VOC image dataset andthe YouTube-Objects video dataset, and it demonstrates superior performance over recent state-of-the-art approaches.