In this paper, we propose a novel guided normal filtering followed by vertex updating for mesh denoising. We introduce a two-stage scheme to construct adaptive consistent neighborhoods for guided normal filtering. In the first stage, we newly design a consistency measurement to select a coarse consistent neighborhood for each face in a patch-shift manner. In this step, the selected consistent neighborhoods may still contain some features. Then, a graph-cut based scheme is iteratively performed for constructing different adaptive neighborhoods to match the corresponding local shapes of the mesh. The constructed local neighborhoods in this step, known as the adaptive consistent neighborhoods, can avoid containing any geometric features. By using the constructed adaptive consistent neighborhoods, we compute a more accurate guide normal field to match the underlying surface, which will improve the results of the guide normal filtering. With the help of the adaptive consistent neighborhoods, our guided normal filtering can preserve geometric features well, and is robust against complex shapes of surfaces. Intensive experiments on various meshes show the superiority of our method visually and quantitatively.