We provide a first calculation of the complete next-to-leading order QCD corrections for heavy flavor contributions to the inclusive structure function $g_1$ in longitudinally polarized deep-inelastic scattering. The results are derived with largely analytical methods and retain the full dependence on the heavy quark's mass. We discuss all relevant technical details of the calculation and present numerical results for the heavy quark scaling functions. We perform important crosschecks to verify our results in the known limit of photoproduction and for the unpolarized electroproduction of heavy quarks. We also compare our calculations to the available, partial results in the polarized case, in particular, in the limit of asymptotically large photon virtualities. First steps towards phenomenological applications are taken by providing some estimates for inclusive charm production in polarized deep-inelastic scattering at a future electron-ion collider and studying their sensitivity to the polarized gluon distribution. The residual dependence of heavy quark electroproduction on unphysical factorization and renormalization scales and on the heavy quark mass is investigated.