Frailty models have become popular in survival analysis for dealing with situations where groups of observations are correlated. If the data comprise only exact or right-censored failure times, inference can be done by either integrating out the frailties directly or by using the EM algorithm. If there is both left- and right-censoring this is no longer the case. However the MCMC method of Clayton (1991, Biometrics 47, 467-485) can be easily extended by imputation of the left-censored times. Several schemes for doing this are suggested and compared. Application of the methods is illustrated using data on the joint failures of patients with fibrodysplasia ossificans progressiva.