The variance-covariance matrix for multiple stochastic processes is of great interest in most financial applications, such as portfolio selection and risk management. One needs to estimate the covariance of a pair of security prices when the processes are observed at random times with noise. We propose a new estimator for this covariance, called the random lead-lag estimator, derive its properties and compare it to some other estimators that have been proposed recently.