Background: Triple-negative breast cancer (TNBC) represents a heterogeneous group of ER- and HER2-negative tumors with poor clinical outcome. We recently reported that Pten-loss cooperates with low expression of microRNA-145 to induce aggressive TNBC-like lesions in mice. To systematically identify microRNAs that cooperate with PTEN-loss to induce aggressive human BC, we screened for miRNAs whose expression correlated with PTEN mRNA levels and determined the prognostic power of each PTEN-miRNA pair alone and in combination with other miRs. Methods: Publically available data sets with mRNA, microRNA, genomics, and clinical outcome were interrogated to identify miRs that correlate with PTEN expression and predict poor clinical outcome. Alterations in genomic landscape and signaling pathways were identified in most aggressive TNBC subgroups. Connectivity mapping was used to predict response to therapy. Results: In TNBC, PTEN loss cooperated with reduced expression of hsa-miR-4324, hsa-miR-125b, hsa-miR-381, hsa-miR-145, and has-miR136, all previously implicated in metastasis, to predict poor prognosis. A subgroup of TNBC patients with PTEN-low and reduced expression of four or five of these miRs exhibited the worst clinical outcome relative to other TNBCs (hazard ratio (HR) = 3.91; P < 0.0001), and this was validated on an independent cohort (HR = 4.42; P = 0.0003). The PTEN-low/miR-low subgroup showed distinct oncogenic alterations as well as TP53 mutation, high RB1-loss signature and high MYC, PI3K, and β-catenin signaling. This lethal subgroup almost completely overlapped with TNBC patients selected on the basis of Pten-low and RB1 signature loss or β-catenin signaling-high. Connectivity mapping predicted response to inhibitors of the PI3K pathway. Conclusions: This analysis identified microRNAs that define a subclass of highly lethal TNBCs that should be prioritized for aggressive therapy.