Current brachytherapy dose calculations ignore applicator attenuation and tissue heterogeneities, assuming isolated sources embedded in unbounded medium. Conventional Monte Carlo (MC) dose calculations, while accurate, are too slow for practical treatment planning. This study evaluates the efficacy of correlated sampling in reducing the variance of MC photon transport simulation in typical brachytherapy geometries. Photon histories were constructed in the homogeneous geometry and weight correction factors applied to account for the perturbing effect of heterogeneities. Two different estimators, expected value track-length (ETL) and analogue (ANL), were used. The method was tested for disc-shaped heterogeneities and point-isotropic sources as well as for a model 6702 125I seed. Uncorrelated ETL estimation was 10-100 times more efficient than its ANL counterpart. Correlated ETL estimation offered efficiency gains as large as 104 in regions where dose perturbations are small (<5%). For perturbations of 40-50%, efficiency gains were in some cases even less than unity. However, correlated ETL was capable of producing less than 2% (1 standard deviation) uncertainty in more than 90% of the voxels in 1 CPU hour. Correlated sampling significantly improves efficiency under selected circumstances and, in combination with other variance reduction strategies, may make MC-based treatment planning a reality for brachytherapy.