The effective population size Embedded Image is a key parameter in population genetics and evolutionary biology, as it quantifies the expected distribution of changes in allele frequency due to genetic drift. Several methods of estimating Embedded Image have been described, the most direct of which uses allele frequencies measured at two or more time points. A new likelihood-based estimator Embedded Image for contemporary effective population size using temporal data is developed in this article. The existing likelihood methods are computationally intensive and unable to handle the case when the underlying Embedded Image is large. This article tries to work around this problem by using a hidden Markov algorithm and applying continuous approximations to allele frequencies and transition probabilities. Extensive simulations are run to evaluate the performance of the proposed estimator Embedded Image, and the results show that it is more accurate and has lower variance than previous methods. The new estimator also reduces the computational time by at least 1000-fold and relaxes the upper bound of Embedded Image to several million, hence allowing the estimation of larger Embedded Image. Finally, we demonstrate how this algorithm can cope with nonconstant Embedded Image scenarios and be used as a likelihood-ratio test to test for the equality of Embedded Image throughout the sampling horizon. An R package “NB” is now available for download to implement the method described in this article.