Bose-Einstein correlations have been measured using samples of proton-proton collisions at 0.9 and 2.36 TeV center-of-mass energies, recorded by the CMS experiment at the CERN Large Hadron Collider. The signal is observed in the form of an enhancement of pairs of same-sign charged particles with small relative four-momentum. The size of the correlated particle emission region is seen to increase significantly with the particle multiplicity of the event.