Abstract An exact algorithm for estimating the dynamic stochastic block model is proposed. This model assumes a hidden Markov chain for the evolution of the social behavior of a group of individuals at repeated time occasions and may be used to assign these individuals to the latent blocks in a dynamic fashion. For the estimation of this model, the proposed exact algorithm maximizes the target function introduced by Matias and Miele [7]. This function is derived from a variational approximation of the model log-likelihood, based on the assumption that the latent variables identifying the blocks are a posteriori independent across individuals, but not across time occasions. A simulation study is performed to compare the exact algorithm with the approximate maximization algorithm proposed by Matias and Miele [7]. Results show that there is a certain advantage of the first in terms of dynamic assignment of individuals to the latent blocks in comparison to the true blocking structure, as measured by the adjusted Rand index.