In this paper, we consider structure detection and parameter estimation of the nonlinear autoregressive with exogenous inputs (NARX) model, using the EM (expectation-maximisation) algorithm. The parameter estimation step uses particle smoothing to obtain the necessary expectations in the E-step and the parameters are then estimated in closed form in the M-step. The model structure detection is performed using an F-test, which makes use of the parameter information matrix (inverse of the covariance matrix), obtained from an augmentation of the EM algorithm. The steps for obtaining the information matrix are robust, guaranteeing a positive semi-definite information matrix to use in the structure detection step. For the case of unknown model orders, a method is proposed using the stochastic complexity (SC) information criterion for selecting between candidate models. The SC is composed of the information matrix (representing model complexity) and a likelihood estimate (representing model accuracy), which are both generated as byproducts of the augmented EM algorithm. Numerical results demonstrate that the EM approach performs well in comparison to a standard alternative based on orthogonal least squares, and also avoids the need to estimate a noise model for the case of measurement noise corrupted output signals. (C) 2012 Elsevier Ltd. All rights reserved.