Timely regional air quality forecasting in a city is crucial and beneficial for supporting environmental management decisions as well as averting serious accidents caused by air pollution. Artificial Intelligence-based models have been widely used in air quality forecasting. The Shallow Multi-output Long Short-Term Memory (SM-LSTM) model is suitable for regional multi-step-ahead air quality forecasting, while it commonly encounters spatio-temporal instabilities and time-lag effects. To overcome these bottlenecks and overfitting issues, this study proposed a Deep Multi-output LSTM (DM-LSTM) neural network model that were incorporated with three deep learning algorithms (i.e., mini-batch gradient descent, dropout neuron and L2 regularization) to configure the model for extracting the key factors of complex spatio-temporal relations as well as reducing error accumulation and propagation in multi-step-ahead air quality forecasting. The proposed DM-LSTM model was evaluated by three time series of PM2.5, PM10, and NOx simultaneously at five air quality monitoring stations in Taipei City of Taiwan. Results indicated that the loss function values (mean-square-error) of the SM-LSTM and DM-LSTM models in the testing stages at horizon t+4 were 0.87 and 0.72, respectively. The Gbench values of the DM-LSTM model in the testing stages for PM2.5, PM10, and NOx reached 0.95 at horizon t+1 and exceeded 0.81 at horizon t+4, respectively. Results demonstrated that the proposed DM-LSTM model incorporated with three deep learning algorithms could significantly improve the spatio-temporal stability and accuracy of regional multi-step-ahead air quality forecasts.