In this paper, we present multinomial latent logistic regression (MLLR), a new learning paradigm that introduces latent variables to logistic regression. By inheriting the advantages of logistic regression, MLLR is efficiently optimized using the second-order derivatives and provides effective probabilistic analysis on output predictions. MLLR is particularly effective in weakly supervised settings where the latent variable has an exponential number of possible values. The effectiveness of MLLR is demonstrated on four different image understanding applications, including a new challenging architectural style classification task. Furthermore, we show that MLLR can be generalized to general structured output prediction, and in doing so, we provide a thorough investigation of the connections and differences between MLLR and existing related algorithms, including latent structural SVMs and hidden conditional random fields.