Nonlinear system identification is discussed in a mixed set-membership and statistical setting. A Markov chain Monte Carlo (MCMC) approach is proposed that estimates the feasible parameter set, the minimum volume outer-bounding ellipsoid and the minimum variance estimate. The proposed algorithm is proved to be convergent and enjoys some desirable properties. Further, its computational complexity and numerical accuracy are studied.