Advances in RNA sequencing (RNA-Seq) have facilitated transcriptomic analysis of plasma for the discovery of new diagnostic and prognostic markers for disease. We aimed to develop a short-read RNA-Seq protocol to detect mRNAs, long non-coding RNAs (lncRNAs) and circular RNAs (circRNAs) in plasma for the discovery of novel markers for coronary artery disease (CAD) and heart failure (HF). Circulating cell-free RNA from 59 patients with stable CAD (half of whom developed HF within 3 years) and 30 controls was sequenced to a median depth of 108 paired reads per sample. We identified fragments from 3986 messenger RNAs (mRNAs), 164 long non-coding RNAs (lncRNAs), 405 putative novel lncRNAs and 227 circular RNAs in plasma. Circulating levels of 160 mRNAs, 10 lncRNAs and 2 putative novel lncRNAs were altered in patients compared with controls (absolute fold change >1.2, p < 0.01 adjusted for multiple comparisons). The most differentially abundant transcripts were enriched in mRNAs encoded by the mitochondrial genome. We did not detect any differences in the plasma RNA profile between patients who developed HF compared with those who did not. In summary, we show that mRNAs, lncRNAs and circular RNAs can be reliably detected in plasma by deep RNA-Seq. Multiple coding and non-coding transcripts were altered in association with CAD, including several mitochondrial mRNAs, which may indicate underlying myocardial ischaemia and oxidative stress. If validated, circulating levels of these transcripts could potentially be used to help identify asymptomatic individuals with established CAD prior to an acute coronary event.