Self-assembly of organized molecular structures on insulators is technologically very relevant, but in general rather challenging to achieve due to the comparatively weak molecule-substrate interactions. Here the self-assembly of a bimolecular hydrogen-bonded network formed by melamine (M) and cyanuric acid (CA) on ultrathin NaCl films grown on a Au(111) surface is reported. Using scanning tunneling microscopy under ultrahigh-vacuum conditions it is demonstrated that it is possible to exploit strong intermolecular forces in the M-CA system, resulting from complementary triple hydrogen bonds, to grow 2D bimolecular networks on an ultrathin NaCl film that are stable at a relatively high temperature of approximately 160 K and at a coverage below saturation of the first molecular monolayer. These hydrogen-bonded structures on NaCl are identical to the self-assembled structures observed for the M-CA system on Au(111), which indicates that the molecular self-assembly is not significantly affected by the isolating NaCl substrate.