Motivated by the state of the art method for producing boron nitride nanotubes in which magnesium has been speculated to act as a catalyst, we study the elemental chemistry of boron and nitrogen on the Mg(0001) surface using ab initio methods. We do this by considering the energetics of individual boron and nitrogen atoms, and the smallest boron and nitrogen containing molecules. We observe that magnesium promotes boron-nitride (BN) molecule formation on the catalyst surface. Based on the analysis of the behavior of BN molecules on the catalyst surface, we propose a possible route for further development of hexagonal BN sheets mediated by the catalyst