Our interest in the mechanisms of atherosclerosis progression (ATHp) has led to the recent identification of 13 miRNAs and 1285 mRNAs whose expression was altered during ATHp. Here, we deepen the functional relationship among these 13 miRNAs and genes associated to oxidative stress, a crucial step in the onset and progression of vascular disease. We first compiled a list of genes associated to the response to oxidative stress (Oxstress genes) by performing a reverse Gene Ontology analysis (rGO, from the GO terms to the genes) with the GO terms GO0006979, GO1902882, GO1902883 and GO1902884, which included a total of 417 unique Oxstress genes. Next, we identified 108 putative targets of the 13 miRNAs among these unique Oxstress genes, which were validated by an integrated miRNA/mRNA counter-expression analysis with the 1285 mRNAs that yielded 14 genes, Map2k1, Mapk1, Mapk9, Dapk1, Atp2a2, Gata4, Fos, Egfr, Foxo1, Ccr7, Vkorc1l1, Rnf7, Kcnh3, and Mgat3. GO enrichment analysis and a protein–protein-interaction network analysis (PPI) identified most of the validated Oxstress transcripts as components of signaling pathways, highlighting a role for MAP signaling in ATHp. Lastly, expression of these Oxstress transcripts was measured in PBMCs from patients suffering severe coronary artery disease, a serious consequence of ATHp. This allowed the identification of FOXO1 and CCR7 as blood markers downregulated in CAD. These results are discussed in the context of the interaction of the Oxstress transcripts with the ATHp-associated miRNAs.