Sachverhalt: A. M._ hatte sich bei Unfällen am 27. Juli 1972 und am 9. November 1975 je eine Knieverletzung rechts zugezogen, für deren Folgen die Schweizerische Unfallversicherungsanstalt (SUVA) Versicherungsleistungen erbrachte. Nach mehreren Rückfällen und nach Einsetzen einer Knietotalprothese rechts am 24. Oktober 2002 bezieht M._ seit 1. Juni 2004 eine Invalidenrente der Unfallversicherung basierend auf einer Erwerbsunfähigkeit von 26%. Im Sommer 2009 machte M._ einen weiteren Rückfall geltend. Nach diversen Untersuchungen, mehreren operativen Eingriffen sowie einer kreisärztlichen Untersuchung vom 24. November 2011 erhöhte die SUVA mit Verfügung vom 4. Mai 2012 die Rente mit Wirkung ab 1. Dezember 2011 auf 31%, was sie mit Einspracheentscheid vom 17. September 2012 bestätigte. B. Die dagegen erhobene Beschwerde hiess das Kantonsgericht Basel-Landschaft mit Entscheid vom 28. Februar 2013 insoweit teilweise gut, als es den Beginn des Anspruchs auf die erhöhte Rente auf 1. Oktober 2009 festlegte. Soweit M._ eine höhere Rente beantragte, wies das kantonale Gericht die Beschwerde ab. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragt die SUVA, der angefochtene Entscheid sei in Bezug auf den Zeitpunkt der Rentenerhöhung aufzuheben und der Einspracheentscheid vom 17. September 2012 sei zu bestätigen. M._ lässt auf Abweisung der Beschwerde schliessen, während die Vorinstanz und das Bundesamt für Gesundheit (BAG) auf eine Vernehmlassung verzichten. 