We report on a joint experimental and theoretical study of the ordered structures of melamine molecules formed on the Au(111)-(22 x root 3) surface. Scanning tunneling microscopy (STM) images taken under UHV conditions reveal two distinct monolayers one of which has never been reported before on gold. We also find that one of the structures may serve as a transition region ("domain wall") between islands formed by the other arrangement. Using state-of-the-art density functional calculations in conjunction with a systematic gas-phase analysis based on considering all planar structures melamine molecules can form with each other, we propose atomistic models for both structures and the transition region.