The lattice thermal conductivity of the candidate thermoelectric material Mg$_3$Sb$_2$ is studied from first principles, with the inclusion of anharmonic, isotope, and boundary scattering processes, and via an accurate solution of the Boltzmann equation. We find that the anomalously low observed conductivity is due to grain-boundary scattering of phonons, whereas the purely anharmonic conductivity is an order of magnitude larger. Mass disorder due to alloying and off-stoichiometry is also found to contribute significantly to its decrease. Combining ab initio values vs sample size with measured grain-size distributions, we obtain an estimate of $kappa$ vs T in nano-polycrystalline material in good agreement with typical experiments, and compute the ZT figure of merit in the various cases.