Latent Gaussian models (LGMs) are widely used in statistics and machine learning. Bayesian inference in non-conjugate LGMs is difficult due to intractable integrals in- volving the Gaussian prior and non-conjugate likelihoods. Algorithms based on variational Gaussian (VG) approximations are widely employed since they strike a favorable bal- ance between accuracy, generality, speed, and ease of use. However, the structure of the optimization problems associated with these approximations remains poorly understood, and standard solvers take too long to con- verge. We derive a novel dual variational in- ference approach that exploits the convexity property of the VG approximations. We ob- tain an algorithm that solves a convex op- timization problem, reduces the number of variational parameters, and converges much faster than previous methods. Using real- world data, we demonstrate these advantages on a variety of LGMs, including Gaussian process classification, and latent Gaussian Markov random fields.