Cold atoms trapped in a conservative potential can be used for quantum information processing, where their high density can be employed to achieve high efficiency in quantum operations. The high atomic density, on the other hand, alters the atomic coherence dynamics and leads to a surprising prolongation of the coherence times, a phenomenon we call collisional narrowing in analog to the well known motional narrowing effect in NMR. Here we present our theoretical and experimental study of collisional narrowing in optically trapped atoms. We show that elastic collisions reduce the spread of the atomic phase distribution and modify its time evolution from ballistic to diffusive. We perform Ramsey experiments on cold ⁸⁷Rb atoms trapped in a far-off-resonance laser, and observe a decrease of the dephasing rate for an increasing collision rate. We also show that the new emerging dephasing timescale depends only on the atomic phase space density of the ensemble. Finally, a general model of an ensemble of two level systems undergoing discrete randomizing events with Poisson statistics is solved and a general formula is derived in which the line shape is expressed in terms of the "bare" spectrum and the Poisson rate constant. This theory applies to a wide range of systems in which the spectrum is modified under random recurring events.