Background: In the triple-negative breast cancer (TNBC) group, the luminal androgen receptor subtype is characterized by expression of androgen receptor (AR) and lack of estrogen receptor and cytokeratin 5/6 expression. Cathepsin D (Cath-D) is overproduced and hypersecreted by breast cancer (BC) cells and is a poor prognostic marker. We recently showed that in TNBC, Cath-D is a potential target for antibody-based therapy. This study evaluated the frequency of AR/Cath-D co-expression and its prognostic value in a large series of patients with non-metastatic TNBC. Methods: AR and Cath-D expression was evaluated by immunohistochemistry in 147 non-metastatic TNBC. The threshold for AR positivity (AR+) was set at ≥1% of stained cells, and the threshold for Cath-D positivity (Cath-D+) was moderate/strong staining intensity. Lymphocyte density, macrophage infiltration, PD-L1 and programmed cell death (PD-1) expression were assessed. Results: Scarff-Bloom-Richardson grade 1–2 and lymph node invasion were more frequent, while macrophage infiltration was less frequent in AR+/Cath-D+ tumors (62.7%). In multivariate analyses, higher tumor size, no adjuvant chemotherapy and AR/Cath-D co-expression were independent prognostic factors of worse overall survival. Conclusions: AR/Cath-D co-expression independently predicted overall survival. Patients with TNBC in which AR and Cath-D are co-expressed could be eligible for combinatory therapy with androgen antagonists and anti-Cath-D human antibodies.