Sachverhalt: A. Am 30. August 1966 erteilte die Kantonale Baukommission des Kantons Wallis dem damaligen Eigentümer des ausserhalb der Bauzone der Einwohnergemeinde (EG) Zermatt gelegenen Grundstücks Nr. xxx, Plan Nr. yyy, die Bewilligung zum Bau eines "Walliser Stadels". Im November 1998 erwarb Y._ die Liegenschaft und reichte am 9. Juli 1999 bei der EG Zermatt ein Ausnahmegesuch für ein Umbauprojekt ein. Ohne die Baubewilligung abzuwarten, begann er mit den Umbauarbeiten, weshalb die Kantonale Baukommission die Arbeiten am 25. August 1999 einstellen liess. Mit Verfügung vom 19. April 2000 erteilte die Kantonale Baukommission die Bewilligung zum Um- und Anbau des bestehenden Gebäudes sowie zur Nutzung als Restaurant. Nachdem am 4. Mai 2000 die öffentlich-rechtliche Eigentumsbeschränkung des Zweckänderungs- und des Veräusserungsverbots zu Spekulationszwecken im Grundbuch eingetragen worden war, stellte die Kantonale Baukommission die Baubewilligung am 24. Mai 2000 zu. B. Am 28. Juli 2000 reichte Y._ ein weiteres Baugesuch zum Umbau des Restaurants ein, wobei er insbesondere um die Bewilligung für ein vollständiges Untergeschoss und diverse Fassadenänderungen ersuchte. Y._ begann wiederum, ohne den Baubewilligungsentscheid abzuwarten, mit den Umbauarbeiten. Die Kantonale Baukommission liess deshalb am 22. September 2000 die Arbeiten einstellen. Mit Verfügung vom 6. Februar 2001 verweigerte die Kantonale Baukommission die Baubewilligung mit der Begründung, das Bauvorhaben sei weder zonenkonform noch standortgebunden und komme zudem teilweise ins Waldareal zu stehen. Am 28. Februar 2001 teilte die EG Zermatt mit, dass der Bau, für den die Bewilligung verweigert worden war, erstellt und in Betrieb genommen worden sei. C. Mit Verfügung vom 10. März 2004 verzichtete die Kantonale Baukommission auf die Wiederherstellung des rechtmässigen Zustands, da diese weder verhältnismässig sei noch im öffentlichen Interesse liege; zugleich verurteilte sie die Bauherrschaft zu einer Busse von Fr. 50'000.--. Gegen diese Verfügung reichte Y._ am 8. April 2004 beim Staatsrat des Kantons Wallis eine Beschwerde ein, welche er jedoch wieder zurückzog, sodass das Verfahren am 17. Februar 2006 abgeschrieben wurde. D. Mit Kaufvertrag vom 5. Oktober 2004 verpflichtete sich Y._, dem Ehepaar AX._ und BX._ die Parzelle Nr. xxx zum Preis von Fr. 950'000.-- zu verkaufen. Der Notar wurde beauftragt, eine vom Verkäufer zu bezahlende Busse vom Verkaufspreis abzuziehen und diese Busse direkt den zuständigen Behörden zu überweisen. Aufgrund der Eigentumsbeschränkung (vgl. Sachverhalt lit. A. hiervor) verweigerte das Grundbuchamt in der Folge die Eintragung des Kaufvertrags. Gestützt auf den Entscheid des Staatsrats vom 12. Mai 2010 wurden AX._ und BX._ schliesslich am 22. Juli 2010 als neue Eigentümer im Grundbuch eingetragen. E. Am 17. Mai 2005 forderte die Kantonale Baukommission Y._ auf, ein Baugesuch einzureichen, da gemäss der Mitteilung der EG Zermatt das Restaurant in der Zwischenzeit zu einem Wohnhaus umgebaut worden sei. Am 3. Juni 2005 reichte Y._ ein nachträgliches Baugesuch zur Umnutzung des Restaurants zu Wohnraum ein. Ersucht wurde insbesondere um Bewilligung von zwei Zimmern und sanitären Einrichtungen im Untergeschoss. F. Nach Durchführung eines Vernehmlassungsverfahrens verweigerte die Kantonale Baukommission mit Verfügung vom 9. Januar 2009 die nachgesuchte Baubewilligung für den Umbau des Restaurants zu Wohnzwecken. Auf die Wiederherstellung des Erdgeschosses in den am 19. April 2000 bewilligten Zustand wurde verzichtet. Hingegen wurde Y._ aufgefordert, den rechtmässigen Zustand insoweit wiederherzustellen, als dass innert sechs Monaten nach Eintritt der Rechtskraft der Verfügung die folgenden Wiederherstellungsarbeiten auszuführen seien: das Untergeschoss darf bestehen bleiben, jedoch wird die Benutzung zu Wohnzwecken untersagt und die Zimmer sind zurückzubauen, lediglich die Innentreppe wird toleriert; die Aussentreppe im Norden ist abzubrechen; die Zugangstüre zum Untergeschoss sowie das danebenliegende Fenster auf der Nordseite sind zuzumauern. Der Aushub an dieser Stelle ist zuzuschütten; die Sanitäreinrichtungen (Bad, Dusche, WC) im Untergeschoss sind zu entfernen; der Heizungsraum im Untergeschoss kann als solcher bestehen bleiben; der Lichtschacht auf der Ostseite und sein Geländer sind abzureissen, das Fenster zuzumauern und der Aushub aufzufüllen; die Steinterrassen sind auf einen Zugangsweg von 1.20 m Breite zu reduzieren; die Feuerstellen (Cheminée oder Grill) im Aussenbereich sind zu entfernen; das Vordach ist auf das Mass laut Bewilligung vom 19. April 2000 zu kürzen; sämtliche Umgebungsarbeiten sind zurückzubauen und das Gelände ist in einen naturnahen Zustand zurückzuführen." G. Gegen diese Verfügung erhob Y._ am 2. März 2009 beim Staatsrat Beschwerde. Er machte geltend, dass im Zeitpunkt der Verfügung der Kantonalen Baukommission vom 10. März 2004 (vgl. Sachverhalt lit. C. hiervor) die Umnutzung des Restaurants zu Wohnraum bereits vollzogen gewesen sei, sodass mit der Wiederherstellungsverfügung vom 9. Januar 2009 der Grundsatz der Rechtswirksamkeit von Verwaltungsverfügungen verletzt werde. Das von ihm gestellte Abänderungsgesuch vom 3. Juni 2005 sei deshalb nicht mehr notwendig gewesen. Im Übrigen sei die Wiederherstellung nicht verhältnismässig und verletze den Vertrauensgrundsatz. Mit Entscheid vom 12. Mai 2010 wies der Staatsrat die Beschwerde ab und erwog, dass die Nutzungsänderung eine Baubewilligung erfordere und keine abgeurteilte Sache vorliege. Aufgrund der baulichen Änderungen komme Art. 24a RPG (SR 700) nicht zur Anwendung. Für ein Bergrestaurant bestehe eine gewisse Standortgebundenheit im Sinne von Art. 24 RPG, was bei einer Wohnnutzung nicht der Fall sei. Angesichts der massiven Abweichung vom Erlaubten sei die verfügte Wiederherstellung verhältnismässig. H. Mit Eingabe vom 17. Juni 2010 führte Y._ gegen diesen Entscheid Verwaltungsgerichtsbeschwerde ans Kantonsgericht Wallis. Dieses verfügte am 5. Juli 2010 unter Hinweis auf den Entscheid des Staatsrats vom 12. Mai 2010, wonach die Ehegatten AX._ und BX._ als neue Eigentümer der Parzelle Nr. xxx im Grundbuch einzutragen seien (vgl. Sachverhalt lit. D. hiervor), dass den neuen Eigentümern im Beschwerdeverfahren Parteistellung zukomme. Zugleich setzte es AX._ und BX._ Frist bis zum 6. September 2010 an, um allfällige Rechtsbegehren in dieser Angelegenheit zu stellen. AX._ und BX._ liessen sich in der Folge nicht vernehmen oder vertreten. Mit Urteil vom 22. Dezember 2010 wies das Kantonsgericht die Beschwerde von Y._ ab. Die Frist zur Wiederherstellung des rechtmässigen Zustandes gemäss der Verfügung der Kantonalen Baukommission vom 9. Januar 2009 setzte das Kantonsgericht auf sechs Monate nach Eintritt der Rechtskraft des vorliegenden Urteils fest. I. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten, eventuell subsidiärer Verfassungsbeschwerde, vom 2. Februar 2011 beantragen die Eigentümer der Liegenschaft, AX._ und BX._, das Urteil des Kantonsgerichts vom 22. Dezember 2010 sei aufzuheben und die Angelegenheit zu neuer Entscheidung an die Vorinstanz zurückzuweisen. Mit Verfügung vom 28. Februar 2011 erkannte der Präsident der I. öffentlich-rechtlichen Abteilung der Beschwerde aufschiebende Wirkung zu. J. Das Kantonsgericht und der Staatsrat stellen Antrag auf Beschwerdeabweisung. Die Kantonale Baukommission beantragt, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Die Einwohnergemeinde Zermatt verzichtet auf eine Stellungnahme. Y._ beantragt die Gutheissung der Beschwerde. Das Bundesamt für Raumentwicklung ARE reicht eine Stellungnahme ein, verzichtet jedoch auf das Stellen von Anträgen. Die Vernehmlassungen wurden den Beschwerdeführern zur Kenntnisnahme zugestellt.