Carbon-chain anions were recently detected in the interstellar medium. These very reactive species are used as tracers of the physical and chemical conditions in a variety of astrophysical environments. However, the local thermodynamic equilibrium conditions are generally not fulfilled in these environments. Therefore, collisional as well as radiative rates are needed to accurately model the observed emission lines. We determine in this work the state-to-state rate coefficients of C4H- in collision with both ortho- and para-H2. A new ab initio 4D potential energy surface was computed using explicitly correlated coupled-cluster procedures. This surface was then employed to determine rotational excitation and de-excitation cross-sections and rate coefficients for the first 21 rotational levels (up to rotational level j1 = 20) using the close-coupling method, while the coupled-state approximation was used to extend the calculations up to j1 = 30. State-to-state rate coefficients were obtained for the temperature range 2-100 K. The differences between the ortho- and para-H2 rate coefficients are found to be small.