From first-principles density functional theory calculations, we propose hexagonal layered MgB$_3$C$_3$ as a potential phonon-mediated superconductor at 59 K, which is far higher than the superconductivity of MgB$_2$ ($\approx$ 39 K). The MgB$_3$C$_3$ is energetically and dynamically stable at ambient pressure in the \textit{P-62m} hexagonal structure with c/a $\approx$ 0.79 and forms in stacks of honeycomb B-C layers with Mg as a space filler. Band structure calculations indicate that the bands at the Fermi level derive mainly from B and C orbitals in which two $\sigma$- and two $\pi$ bands both contribute to the total density of state. The $\pi$ bands are found to be strongly couple with out-of-plane acoustic phonon mode, while the $\sigma$ bands coupled with the in-plane bond-stretching optical E$^{\prime} $ phonon modes produces a sizable superconductivity in MgB$_3$C$_3$.