In this paper we report our development of a new class of hidden Markov models (HMMs) with each state characterized by a time series model which is non-stationary up to the second order. A close-form solution for the model parameter estimation is obtained based on the EM algorithm and on the matrix-calculus implementation technique. In the first set of evaluation experiments, we adopt the residual square sum, over states and over time frames within state bounds, as a quantitative measure for goodness of fit between the model and the speech data. It is observed that inclusion of state-conditioned second-order non-stationarity, implemented by use of time-varying regression coefficients, has substantially greater effects on reducing data-fitting error than increase of the regression terms while maintaining the coefficients of each term constant. In the second set, isolated-word recognition experiments, it is found that use of mix of first-order and second-order non-stationarities consistently produces higher recognition accuracy than the conventional, stationary-state HMMs.