In this paper, we study an asset-liability management problem under a mean-variance criterion with regime switching. Unlike previous works, the dynamics of assets and liability are described by non-Markovian regime-switching models in the sense that all the model parameters are predictable with respect to the filtration generated jointly by a Markov chain and a Brownian motion. The problem is solved with the aid of backward stochastic differential equations (BSDEs) and bounded mean oscillation martingales. An efficient strategy and an efficient frontier are obtained and represented by unique solutions to several relevant BSDEs. We show that the optimal capital structure can be achieved when the initial asset value is expressed by a linear combination of the initial liability and the expected surplus. It is further found that a mutual fund theorem holds not only for the efficient strategy, but also for the optimal capital structure.