The effect of random coincidences estimation methods on the quantitative accuracy of iterative and analytic reconstruction methods to determine myocardial blood flow (MBF) in PET studies using H215O has been investigated. Dynamic scans were acquired on the EXACT3D PET scanner on pigs after H215O injection (resting and dipyridamole-induced stress). Radioactive microspheres (MS) were used to provide a "gold standard" of MBF values. The online subtraction (OS) and maximum likelihood (ML) methods for estimating randoms were combined with (i) 3D-RP, (ii) FORE + attenuation-weighted OSEM, (iii) FORE-FBP and (iv) 3D-OSEM. Factor images were generated and resliced to short axis images; 16 ROIs were defined in the left myocardium and 2 ROIs in the left and right cavities. ROIs were projected onto the dynamic images to extract time-activity-curves, which were then fitted to a single compartment model to estimate absolute MBF. Microsphere measurements were obtained in a similar way and 64 pairs of measurements were made. The ML method improved the SNR of 3D-RP, FORE-FBP, FORE-OSEM, and 3D-OSEM by 8%, 8%, 7% and 3% respectively. Compared to the OS method, the ML method improved the accuracy of coronary flow reserve values of 3D-OSEM, 3D-RP, FORE-OSEM and FORE-FBP by 9%, 7%, 1% and 3% respectively. Regression analysis provided better correlation with 3D-OSEM and FORE-OSEM when combined with the ML method. We conclude that the ML method for estimating randoms combined with 3D-OSEM and FORE-OSEM delivers the best performance for absolute quantification of MBF using H215O when compared with microsphere measurements.