Standard deterministic autoregressive moving average (ARMA) models consider prediction errors to be unexplainable noise sources. The accuracy of the estimated ARMA model parameters depends on producing minimum prediction errors. In this study, an accurate algorithm is developed for estimating linear and nonlinear stochastic ARMA model parameters by using a method known as fast orthogonal search, with an extended model containing prediction errors as part of the model estimation process. The extended algorithm uses fast orthogonal search in a two-step procedure in which deterministic terms in the nonlinear difference equation model are first identified and then reestimated, this time in a model containing the prediction errors. Since the extended algorithm uses an orthogonal procedure, together with automatic model order selection criteria, the significant model terms are estimated efficiently and accurately. The model order selection criteria developed for the extended algorithm are also crucial in obtaining accurate parameter estimates. Several simulated examples are presented to demonstrate the efficacy of the algorithm.