A mesh structure (graphene nanomesh) was fabricated by Ullmann coupling of hexabromotriphenylene (HBTP) on Au (111) and Cu (111) surfaces. While HBTP molecules deposited on the Au (111) surface formed a hexagonally packed array at room temperature, after annealing at 373 K the mesh structure was formed in which the distance between nanoholes was approximately 0.8 nm. It agreed with the distance between nanoholes in the mesh structure model that was expected to be formed by HBTP molecules. On the other hand, HBTP molecules deposited on the Cu (111) surface at room temperature formed random filament-like aggregates and subsequent annealing did not change the structure. HBTP deposited on the Cu (111) surface at 473 K also formed the mesh structure, which had less irregularly bound molecules and vacancies than that on the Au (111) surface. The Cu (111) surface heated at 473 K during molecular deposition, on which molecular arrangement and orientations were reversely changed during coupling reaction, was better for forming the high quality mesh structure than the Au (111) surface.