We introduce a Bayesian approach for analyzing high-dimensional multinomial data that are referenced over space and time. In particular, we define a multinomial data model with logit link to a latent spatio-temporal mixed effects model. This strategy allows for complex dependencies including nonstationarity in both space and time, asymmetry, non-seprable covariances, and parsimony. We also introduce the use of the conditional multivariate logit-beta distribution into the dependent multinomial data setting, which leads to conjugate full-conditional distributions for use in a Gibbs sampler. We refer to this model as the multinomial spatio-temporal mixed effects model (MN-STM). Additionally, we provide methodological developments including: the derivation of the associated full-conditional distributions, relationships with the multivariate normal distribution, and the stability of the non-stationary vector autoregressive model. We illustrate the MN-STM through simulations and through a demonstration using data from the Longitudinal Employer Household Dynamics (LEHD) program of the U.S. Census Bureau.