The excursion set theory based on spherical or ellipsoidal gravitational collapse provides an elegant analytic framework for calculating the mass function and the large-scale bias of dark matter haloes. This theory assumes that the perturbed density field evolves stochastically with the smoothing scale and exhibits Markovian random walks in the presence of a density barrier. Here, we derive an analytic expression for the halo bias in a new theoretical model that incorporates non-Markovian extension of the excursion set theory with a stochastic barrier. This model allows us to handle non-Markovian random walks and to calculate perturbatively these corrections to the standard Markovian predictions for the halo mass function and halo bias. Our model contains only two parameters: κ, which parametrizes the degree of non-Markovianity and whose exact value depends on the shape of the filter function used to smooth the density field, and a, which parametrizes the degree of stochasticity of the barrier. Appropriate choices of κ and a in our new model can lead to a closer match to both the halo mass function and the halo bias in the latest N-body simulations than the standard excursion set theory