The ability to fabricate nanoscale domains of uniform size in two-dimensional materials could potentially enable new applications in nanoelectronics and the development of innovative metamaterials. However, achieving even minimal control over the growth of two-dimensional lateral heterostructures at such extreme dimensions has proven exceptionally challenging. Here we show the spontaneous formation of ordered arrays of graphene nano-domains (dots), epitaxially embedded in a two-dimensional boron-carbon-nitrogen alloy. These dots exhibit a strikingly uniform size of 1.6 ± 0.2 nm and strong ordering, and the array periodicity can be tuned by adjusting the growth conditions. We explain this behaviour with a model incorporating dot-boundary energy, a moiré-modulated substrate interaction and a long-range repulsion between dots. This new two-dimensional material, which theory predicts to be an ordered composite of uniform-size semiconducting graphene quantum dots laterally integrated within a larger-bandgap matrix, holds promise for novel electronic and optoelectronic properties, with a variety of potential device applications.The nanoscale patterning of two-dimensional materials offers the possibility of novel optoelectronic properties; however, it remains challenging. Here, Camilli et al. show the self-assembly of large arrays of highly-uniform graphene dots imbedded in a BCN matrix, enabling novel devices.