Sachverhalt: A. Die Gemeinde Mund (heute Naters) erteilte C._ am 8. Mai 2007 die Baubewilligung für einen An- und Umbau ihres Ferienhauses auf der in der Bauzone liegenden Parzelle GBV Nr. 2133 im Maiensäss X._ oberhalb des Dorfs. Sie versah die Baubewilligung u.a. mit der Auflage, die erforderlichen Dienstbarkeiten (Näher- und Grenzbaurecht) vor Baubeginn zu Gunsten der Gemeinde im Grundbuch eintragen zu lassen und eine Kopie dieses Eintrages bei der Gemeinde zu hinterlegen (Ziff. 14). Die Baubewilligung wurde am 5. September 2007 eröffnet und erwuchs unangefochten in Rechtskraft. Mit Schreiben vom 16. Juni 2014 teilte B._, Miteigentümer der Parzelle GBV Nr. 2134, der Gemeinde Naters mit, die Umbauarbeiten am Ferienhaus auf der Parzelle GBV Nr. 2133 seien in den Jahren 2010 bis 2011 in Abweichung der bewilligten Pläne ausgeführt worden. Zudem bestehe das notwendige Näherbaurecht zu seiner Parzelle nicht. Anlässlich der am 4. Juli 2014 durchgeführten Baukontrolle stellte die Gemeinde fest, die Baute stimme zwar mit den bewilligten Bauplänen überein und die Näher- und Grenzbaurechte würden vorliegen, jedoch seien sie nicht im Grundbuch eingetragen. Daraufhin stellte B._ den Antrag, der Anbau sei abzubrechen und es sei eine Frist zur Wiederherstellung des ursprünglichen Zustandes zu verfügen. Die Gemeinde teilte C._ mit Schreiben vom 19. Dezember 2014 mit, ihr werde eine Frist bis zum 30. Januar 2015 gewährt, um das Näher- und Grenzbaurecht im Grundbuch eintragen zu lassen. Daraufhin informierte A._ die Gemeinde, dass seine Mutter verstorben sei und bat um eine Fristverlängerung. Mit Schreiben vom 28. Juni 2015 kündigte A._ an, er könne der Aufforderung zur Eintragung der Dienstbarkeiten nicht nachkommen, da sich als einzige Partei B._ weigere, sein Einverständnis zum entsprechenden Dienstbarkeitsvertrag zu geben. Am 13. Juni 2016 verfügte die Gemeinde den Abbruch des Anbaus am Ferienhaus bzw. die Wiederherstellung des rechtmässigen Zustandes. Dagegen erhob A._ am 13. Juli 2016 Beschwerde beim Staatsrat des Kantons Wallis, welcher die Beschwerde am 28. Februar 2018 abwies. Gegen diesen Entscheid reichte A._ am 19. April 2018 Beschwerde beim Kantonsgericht Wallis ein. Dieses wies die Beschwerde mit Entscheid vom 16. November 2018 ab. B. Mit Eingabe vom 7. Januar 2019 führt A._ Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Er beantragt, der Entscheid des Kantonsgerichts vom 16. November 2018 sowie die Verfügung der Einwohnergemeinde Naters vom 13. Juni 2016 seien aufzuheben und die Kosten der kantonalen Verfahren seien B._ aufzuerlegen. Der Beschwerdegegner stellt den Antrag, die Beschwerde abzuweisen. Das Kantonsgericht sowie die Einwohnergemeinde Naters beantragen ebenfalls die Abweisung der Beschwerde. Der Staatsrat des Kantons Wallis verzichtet auf eine Stellungnahme. Der Beschwerdeführer nahm erneut Stellung.