The coalescence of two neutron stars was recently observed in a multi-messenger detection of gravitational wave (GW) and electromagnetic (EM) radiation. Binary neutron stars that merge within a Hubble time, as well as many other compact binaries, are expected to form via common envelope evolution. Yet five decades of research on common envelope evolution have not yet resulted in a satisfactory understanding of the multi-spatial multi-timescale evolution for the systems that lead to compact binaries. In this paper, we report on the first successful simulations of common envelope ejection leading to binary neutron star formation in 3D hydrodynamics. We simulate the dynamical inspiral phase of the interaction between a 12$M_odot$ red supergiant and a 1.4$M_odot$ neutron star for different initial separations and initial conditions. For all of our simulations, we find complete envelope ejection and a final orbital separation of $approx 1.1$-$2.8 R_odot$, leading to a binary neutron star that will merge within 0.01-1 Gyr. We find an $alpha_{rm CE}$-equivalent efficiency of $approx 0.1$-$0.4$ for the models we study, but this may be specific for these extended progenitors. We fully resolve the core of the star to $lesssim 0.005 R_odot$ and our 3D hydrodynamics simulations are informed by an adjusted 1D analytic energy formalism and a 2D kinematics study in order to overcome the prohibitive computational cost of simulating these systems. The framework we develop in this paper can be used to simulate a wide variety of interactions between stars, from stellar mergers to common envelope episodes leading to GW sources.