The strong dependence of the large-scale dark matter halo bias on the (local) non-Gaussianity parameter, f_NL, offers a promising avenue towards constraining primordial non-Gaussianity with large-scale structure surveys. In this paper, we present the first detection of the dependence of the non-Gaussian halo bias on halo formation history using N-body simulations. We also present an analytic derivation of the expected signal based on the extended Press-Schechter formalism. In excellent agreement with our analytic prediction, we find that the halo formation history-dependent contribution to the non-Gaussian halo bias (which we call non-Gaussian halo assembly bias) can be factorized in a form approximately independent of redshift and halo mass. The correction to the non-Gaussian halo bias due to the halo formation history can be as large as 100%, with a suppression of the signal for recently formed halos and enhancement for old halos. This could in principle be a problem for realistic galaxy surveys if observational selection effects were to pick galaxies occupying only recently formed halos. Current semi-analytic galaxy formation models, for example, imply an enhancement in the expected signal of ~23% and ~48% for galaxies at z=1 selected by stellar mass and star formation rate, respectively.