Entanglement of formation quantifies the entanglement of a state in terms of the entropy of entanglement of the least entangled pure state needed to prepare it. An analytical expression for this measure exists only for special cases, and finding a closed formula for an arbitrary state remains an open problem. In this work we focus on two-mode Gaussian states, and we derive narrow upper and lower bounds for the measure that get tight for several special cases. Further, we show that the problem of calculating the actual value of the entanglement of formation for arbitrary two-mode Gaussian states reduces to a trivial single parameter optimization process, and we provide an efficient algorithm for the numerical calculation of the measure.