This paper presents a new sparse signal recovery algorithm using variational Bayesian inference based on the Laplace approximation. The sparse signal is modeled as the Laplacian scale mixture (LSM) prior. The Bayesian inference with the Laplacian models is a challenge because the Laplacian prior is not conjugate to the Gaussian likelihood. To solve this problem, we first introduce the inverse-gamma prior, which is conjugate to the Laplacian prior, to model the distinctive scaling parameters of the Laplacian priors. Then the posterior of the sparse signal, approximated by the Laplace approximation, is found to be Gaussian distributed with the expectation being the result of maximum a posterior (MAP) estimation. Finally the expectation-maximization (EM)-based variational Bayesian (VB) inference is utilized to accomplish the sparse signal recovery with the LSM prior. Since the proposed algorithm is a full Bayesian inference based on the MAP estimation, it achieves both the ability of avoiding structural error from the sparse Bayesian learning and the robustness to noise from the MAP estimation. Analysis on experimental results based on both simulated and measured data indicates that the proposed algorithm achieves the state-of-art performance in terms of sparse representation and de-noising.