  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.
