A high-level ab initio study was conducted over the range of tetraatomic molecules containing H, C, N, and Mg. Potential energy surfaces were analyzed, leading, for selected molecules, to the optimization of their geometry in the lowest singlet and triplet excited states. Reliable ground state rotational constants are given for the most stable species, namely, HMgNC and HMgCN, together with respective anharmonic vibrational frequencies of fundamental, overtone, and combination bands. In addition, potential energy surfaces describing the interaction of HCN or HNC with a single magnesium atom have been investigated.