Using global structure searches, we have explored the structural stability of CaB$3$N$3$, a compound analogous to CaC$6$, under pressure. There are two high-pressure phases with space groups $R3c$ and $Amm2$ that were found to be stable between 29 and 42 GPa, and above 42 GPa, respectively. The two phases show different structural frameworks, analogous to graphitic CaC$6$. Phonon calculations confirm that both structures are also dynamically stable at high pressures. The electronic structure calculations show that the $R3c$ phase is a semiconductor with a band gap of 2.21 eV and that the $Amm2$ phase is a semimetal. These findings help advance our understanding of the Ca-B-N ternary system.