We report the first measurement of the longitudinal double-spin asymmetry $A_{LL}$ for mid-rapidity di-jet production in polarized $pp$ collisions at a center-of-mass energy of $\sqrt{s} = 200$ GeV. The di-jet cross section was measured and is shown to be consistent with next-to-leading order (NLO) perturbative QCD predictions. $A_{LL}$ results are presented for two distinct topologies, defined by the jet pseudorapidities, and are compared to predictions from several recent NLO global analyses. The measured asymmetries, the first such correlation measurements, support those analyses that find positive gluon polarization at the level of roughly 0.2 over the region of Bjorken-$x > 0.05$.