Background: Staging of mammary carcinomas of dogs and cats is not only important for prognostic purposes, but also to guide therapy, in particular regarding adjuvant chemotherapy. The classical staging system relies on T, the clinical tumor size, N, the clinical nodal stage, and M, distant metastasis, evaluated by the clinician. However, a more precise and reliable staging system is applied to human stage I–III breast cancer, i.e., without distant metastasis, in which T is replaced by the pathologic tumor size (pT), and N is replaced by the pathologic nodal stage (pN), both evaluated by the pathologist. This staging system is strongly associated with patient outcomes, and is used to select treatment options. The purpose of this study was to design a histologic staging system for Canine Mammary Carcinomas (CMCs, part 1 of this article), and Feline Mammary Carcinomas (part 2), inspired from human oncology, and to assess its association with patient outcomes. Materials and Methods: This retrospective study included 433 female dogs with a surgically removed CMC. Patient outcomes were recorded over a 2-years follow up period. CMCs were staged according to pT (greatest diameter in millimeters on histological slides), lymphovascular invasion (LVI), and pN (confirmed by cytokeratin AE1/AE3 immunohistochemistry). The histological stages were defined as: Stage 0 (CMCs in situ, surrounded by a continuous layer of p63+ myoepithelial cells), Stage I (pT1 ≤ 20 mm, LVI–, pN0–pNX, where pNX refers to the absence of lymph node sample), Stage II (pT2 > 20 mm, LVI–, pN0–pNX), Stage IIIA (pT1, LVI+, and/or pN+), and Stage IIIB (pT2, LVI+, and/or pN+). Results: Disease-free-interval, overall survival and specific survival significantly differed by histological stage. For specific survival, median survival times and hazard ratios (HR) by Cox proportional hazards regression (p < 0.0001) were: Stage 0 (median survival not reached; HR = 1.00; N = 89; 21% of the dogs), Stage I (1,720 days; HR = 3.05; p = 0.0018; N = 81; 19%), Stage II (1,181 days; HR = 4.39; p < 0.0001; N = 79; 18%), Stage IIIA (348 days; HR = 10.59; p < 0.0001; N = 79; 18%), and Stage IIIB (163 days; HR = 16.59; p < 0.0001; N = 105; 24%). Conclusion: The proposed histological staging system (invasiveness, pT, LVI, pN) is a very strong prognostic factor for CMCs.