Background: Obesity is a risk factor of several types of cancer, including breast cancer. In this study, we aimed to histologically characterize the adipose tissue of the tumor microenvironment (TME) of triple-negative breast cancer (TNBC) in overweight/obese versus normal-weight patients. Methods: TNBC tissue sections from normal-weight (BMI<25) and overweight/obese patients (BMI≥25) were stained with antibodies against CD68, CD163, CD31, CD34, and vimentin. At the invasive tumor front, positive cells were counted in tumor adjacent adipose tissue (AT) and within cancer tissue (CT). Further, the size of the tumor-adjacent and distant mammary adipocytes was determined in perilipin stained sections. Expression of ANGPTL4, CD36 and FABP4, proteins involved in fatty acid metabolism, was analyzed in marginal tumor cells using an immune reactive score. Results: Overweight/obese TNBC patients had significantly larger adipocytes, higher numbers of CD163+ macrophages (BMI<25: 2.80 vs. BMI≥25: 10.45; p = 0.011) and lower numbers of CD31+ (BMI<25: 4.20 vs. BMI≥25: 2.40; p = 0.018) and CD34+ (BMI<25: 14.60 vs. BMI≥25: 5.20; p = 0.045) cells as markers of angiogenesis in the AT as well as a higher frequency of cancer-associated-fibroblast-like cells in the AT and CT (BMI<25: 7.60 vs. BMI≥25: 25.39 in total; p = 0.001). Moreover, expression of CD36 (BMI<25: 2.15 vs. BMI≥25: 2.60; p = 0.041) and ANGPTL4 (BMI<25: 6.00 vs. BMI≥25: 9.80; p = 0.026) was elevated in the TNBC cells of overweight/obese patients. Conclusions: Our data suggest BMI-related changes in the TME of overweight/obese TNBC patients, including hypertrophied adipocytes, reduced vascularization, more M2-like macrophages and CAF-like cells, and an increase in the expression of fatty acid metabolizing proteins in marginal tumor cells, all contributing to a more tumor-promoting, immunosuppressive environment.