A search for the rare decays Bs0→μ+μ- and B0→μ+μ- is performed at the LHCb experiment using data collected in pp collisions corresponding to a total integrated luminosity of 4.4 fb-1. An excess of Bs0→μ+μ- decays is observed with a significance of 7.8 standard deviations, representing the first observation of this decay in a single experiment. The branching fraction is measured to be B(Bs0→μ+μ-)=(3.0±0.6-0.2+0.3)×10-9, where the first uncertainty is statistical and the second systematic. The first measurement of the Bs0→μ+μ- effective lifetime, τ(Bs0→μ+μ-)=2.04±0.44±0.05 ps, is reported. No significant excess of B0→μ+μ- decays is found, and a 95% confidence level upper limit, B(B0→μ+μ-)<3.4×10-10, is determined. All results are in agreement with the standard model expectations.