Staphylococcus pseudintermedius is an opportunistic pathogen that is one of the most frequent causes of infections in dogs. In Europe, there are increasing reports of methicillin-resistant S. pseudintermedius (MRSP), and in Sweden, MRSP has also been more frequently isolated during recent years. However, there is limited knowledge regarding the epidemiology and genetic relationship among the Swedish isolates. This study therefore investigated the genetic relationship of MRSP isolated from companion animals in Sweden. In the study, MRSP isolates taken in the period January 2008–June 2010 from a total of 226 dogs and cats were characterized by spa typing, pulsed-field gel electrophoresis, and antimicrobial susceptibility testing. In addition, the geographical distribution of the isolates based on year of isolation and genetic typing was determined using a geographical information system. One multiresistant clonal lineage dominated among Swedish MRSP isolates, corresponding to the European winning lineage ST71-J-t02-SCCmec II-III. Furthermore, the geographical dissemination of MRSP corresponded to areas with high dog densities, centered on the three major cities in Sweden where the largest animal hospitals are situated.