In this paper, we propose two simulation based maximum likelihood (ML) methods to estimate the direction of arrival (DOA) by a novel combination of the Cross-Entropy (CE) method and the polynomial parameterization scheme. The CE method is an efficient stochastic approximation method for solving both discrete and continuous optimization problems. We bridge the ML approach and the stochastic search algorithm by properly randomizing the desired parameters. Numerical results show that the proposed CE-based algorithms yield highly accurate DOA estimation with fast convergence rate while requiring only linear processing complexity. Compared with the conventional iterative quadratic maximization likelihood (IQML) method, the proposed algorithms can alleviate the error propagation effect in low signal to noise ratio (SNR) region and asymptotically approach the Cramér-Rao bound in high SNR region.