Mammary tumors are a major health threat to women and female dogs. In both, metastasis of the primary tumor to distant organs is the most common cause of tumor-related death. Nevertheless, the molecular mechanisms of tumor metastasis are far from being understood, and it is still unknown why some human and canine carcinomas metastasize and others do not. Using 2D-DIGE and MALDI-TOF-MS we identified 21 proteins with significant changes (fold change >1.5; p < 0.05) in protein expression between metastasizing (n = 6) and nonmetastasizing (n = 6) canine mammary carcinomas. Quantitative RT-PCR was used to identify transcriptional or post-transcriptional regulation of protein expression. Up-regulated proteins in metastatic carcinomas included proliferating cell nuclear antigen, ferritin light chain, bomapin, tropomyosin 3, thioredoxin-containing domain C5, adenosin, ornithine aminotransferase, coronin 1A, RAN-binding protein 1,3-phosphoglycerate dehydrogenase, and eukaryotic translation elongation factor 1. Down-regulated proteins in metastatic carcinomas included calretinin, myosin, light chain 2, peroxiredoxin 6, maspin, ibrinogen beta chain, vinculin, isocitrate dehydrogenase 1, tropomyosin 1, annexin A5, and Rho GTPase activating protein 1. Interestingly, 19 of these 21 proteins have been described with a malignancy-associated expression in human breast cancer and other human cancer types before. Further investigations are now necessary to test whether these markers are of prognostic value for canine mammary carcinomas and whether their expression is directly involved in canine mammary carcinogenesis or represent solely a secondary reactive phenotype.