We study structure formation in the presence of primordial non-Gaussianity of the local type with parameters f_NL and g_NL. We show that the distribution of dark-matter halos is naturally described by a multivariate bias scheme where the halo overdensity depends not only on the underlying matter density fluctuation delta, but also on the Gaussian part of the primordial gravitational potential phi. This corresponds to a non-local bias scheme in terms of delta only. We derive the coefficients of the bias expansion as a function of the halo mass by applying the peak-background split to common parametrizations for the halo mass function in the non-Gaussian scenario. We then compute the halo power spectrum and halo-matter cross spectrum in the framework of Eulerian perturbation theory up to third order. Comparing our results against N-body simulations, we find that our model accurately describes the numerical data for wavenumbers k < 0.1-0.3 h/Mpc depending on redshift and halo mass. In our multivariate approach, perturbations in the halo counts trace phi on large scales and this explains why the halo and matter power spectra show different asymptotic trends for k -> 0. This strongly scale-dependent bias originates from terms at leading order in our expansion. This is different from what happens using the standard univariate local bias where the scale-dependent terms come from badly behaved higher-order corrections. On the other hand, our biasing scheme reduces to the usual local bias on smaller scales where |phi| is typically much smaller than the density perturbations. We finally discuss the halo bispectrum in the context of multivariate biasing and show that, due to its strong scale and shape dependence, it is a powerful tool for the detection of primordial non-Gaussianity from future galaxy surveys.