We present an exact dynamical QCD simulation algorithm for the O(a)-improved Wilson fermion with odd number of flavors. Our algorithm is an extension of the non-Hermitian polynomials HMC algorithm proposed by Takaishi and de Forcrand previously. In our algorithm, the systematic errors caused by the polynomial approximation of the inverse of Dirac operator is removed by a noisy-Metropolis test. For one flavor quark it is achieved by taking the square root of the correction matrix explicitly. We test our algorithm for the case of Nf = 1 + 1 on a moderately large lattice size (16 3 × 48). The Nf = 2 + 1 case is also investigated.