Surface structures play an important role in the practical applications of materials. The synthesis of polymer brushes on a solid surface has emerged as an effective tool for tuning surface properties. The fabrication of polymer brush-based surface nanostructures has greatly facilitated the development of materials with unique surface properties. In this review article, synthetic methods used in the synthesis of polymer brushes, and self-assembly approaches applied in the fabrication of surface nanostructures including self-assembly of polymer brushes, co-assembly of polymer brushes and "free" block copolymer chains, and polymerization induced surface self-assembly, are reviewed. It is demonstrated that polymer brush-based surface nanostructures, including spherical surface micelles, wormlike surface structures, layered structures and surface vesicles, can be fabricated. Meanwhile, the challenges in the synthesis and applications of the surface nanostructures are discussed. This review is expected to be helpful for understanding the principles, methods and applications of polymer brush-based surface nanostructures.