Sachverhalt: A. Am 3. August 2012 reichte Y._ ein Baugesuch für den Abbruch der bestehenden Baute (Scheune/Speicher) und die Erstellung eines Einfamilienhauses auf Parzelle 405 in der Gemeinde Andiast ein. Dagegen erhob X._ am 22. August 2012 Einsprache. Mit Entscheid vom 30. August 2012 wies der Gemeindevorstand Andiast die Einsprache ab, soweit er darauf eintrat, und erteilte die Baubewilligung. B. Dagegen erhob X._ am 6. Dezember 2012 Beschwerde beim Verwaltungsgericht des Kantons Graubünden. Er erhob verschiedene formelle Rügen und machte geltend, dass das Bauvorhaben die maximal zulässige Bruttogeschossfläche (BGF) überschreite; hierfür habe die Gemeinde zu Unrecht eine Ausnahmebewilligung erteilt. Am 30. April 2013 wies das Verwaltungsgericht die Beschwerde ab. C. Dagegen hat X._ am 16. August 2013 Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben. Er beantragt, der Entscheid des Verwaltungsgerichts, der Einspracheentscheid des Gemeindevorstands Andiast vom 30. August 2012 und die Baubewilligung vom gleichen Tag seien aufzuheben bzw. für nichtig zu erklären und die Baubewilligung für das Bauvorhaben von Y._ sei zu verweigern. Überdies beantragt er die Gewährung der aufschiebenden Wirkung. D. Y._ (im Folgenden: der Beschwerdegegner) beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Eventualiter sei die Sache an die Vorinstanz oder die Gemeinde Andiast zur Neubeurteilung zurückzuweisen. Die Gemeinde Andiast hält fest, dass die vom angefochtenen Bauprojekt betroffene Scheune in keinem Inventar schützenswerter Bauten verzeichnet sei und ihr auch keineswegs eine spezielle Bedeutung für das Ortsbild von Andiast zukomme.