Since binary data are ubiquitous in educational, psychological, and social research, methods for effectively exploring the underlying factor structure of such data are still undergoing development (Schilling and Bock 2005; Maydeu- Olivares and Joe 2005; and Song and Lee 2005). Two distinct types of methods have been developed, those relying on limited information from low-order marginal and joint frequency responses and those relying on the frequencies of all distinct item response vectors. The latter approach, a full information approach to binary factor analysis, has good optimality properties but is computationally demanding. Meng and Schilling (1996) developed a Monte Carlo EM (MCEM) fitting method for this model. Compared with the Gauss-Hermite method proposed by Bock and Aitkin (1981), the MCEM method is more stable and computationally easier. Under the MCEM framework, the E step is completed by approximating the conditional expectations through observations that are simulated by Markov Chain Monte Carlo methods, while the M step is completed by conditional maximization. In the E step proposed by Meng and Schilling (1996), respondents with the same response pattern are given the same latent factor scores. When there are many very difficult or easy items, this may dramatically decrease the number of response patterns and potentially cause the method to become less stable and accurate. This paper proposes a new E step for the MCEM method to avoid this problem. Simulation studies verify that the new method yields improved results. Possible follow up research also is discussed.