The two-point clustering of dark matter halos is influenced by halo properties besides mass, a phenomenon referred to as halo assembly bias. Using the depth of the gravitational potential well, $V_{rm max}$, as our secondary halo property, in this paper we present the first study of the scale-dependence assembly bias. In the large-scale linear regime, $rgeq10h^{-1}{rm Mpc},$ our findings are in keeping with previous results. In particular, at the low-mass end ($M_{rm vir}<M_{rm coll}approx10^{12.5}{rm M}_{odot}$), halos with high-$V_{rm max}$ show stronger large-scale clustering relative to halos with low-$V_{rm max}$ of the same mass, this trend weakens and reverses for $M_{rm vir}geq M_{rm coll}.$ In the nonlinear regime, assembly bias in low-mass halos exhibits a pronounced scale-dependent bump at $500h^{-1}{rm kpc}-5h^{-1}{rm Mpc},$ a new result. This feature weakens and eventually vanishes for halos of higher mass. We show that this scale-dependent signature can primarily be attributed to a special subpopulation of ejected halos, defined as present-day host halos that were previously members of a higher-mass halo at some point in their past history. A corollary of our results is that galaxy clustering on scales of $rsim1-2h^{-1}{rm Mpc}$ can be impacted by up to $sim15%$ by the choice of the halo property used in the halo model, even for stellar mass-limited samples.