Coronary artery-bypass-graft (CABG) surgery is associated with myocardial damage and increased blood concentrations of circulating microRNAs (miRNA). However, whether and to what extent these miRNAs relate to cardiac tissue miRNA expression have not yet been explored. Since plasma miRNA quantification in samples from cardiopulmonary bypass (CPB) patients is severely hampered by heparin, we established and validated successfully a protocol to reliably measure miRNA in 49 heparinized patients undergoing CABG so as to investigate the relationship between circulating and right atrial miRNAs. Plasma and right atrial expression of miR-1, miR-133a, miR-423-5p, and miR-499 were measured before and after CPB, as well as miRNAs in plasma 24 h thereafter. All plasma miRNAs increased significantly with surgery while cardiac tissue expression of only miR-133a (1.4-fold; p = 0.003) and miR-423-5p (1.3 fold; p = 0.025) increased as well. Right atrial and plasma miR-133a expression correlated positively before CPB (r = 0.288, p = 0.045) but miR-499 expression inversely (r = -0.484, p = 0.0004). There was a strong association between plasma miR-133a and miR-499 concentrations and postoperative troponin I concentrations, the marker for myocardial damage. Increased myocardial miR-133a and miR-423-5p expression together with unchanged miR-1 and miR-499 expression might suggest active release of these miRNAs rather than their origin from damaged cells.