Sachverhalt:
A.
Die A._ AG ist Eigentümerin von Parzelle 125 mit dem darauf gelegenen Hotel- und Restaurationsgebäude in der Landwirtschaftszone der heutigen Gemeinde Obersaxen Mundaun (früher: Gemeinde Surcuolm bzw. Gemeinde Mundaun).
Auf dieser Parzelle war 1977 eine Schiessanlage mit Restaurant und Unterkunftsräumen bewilligt worden; 1978 bewilligte die Gemeinde mit Zustimmung des damaligen Amtes für Gewässerschutz einen Bar- und Dancingbetrieb. 1986 stimmte die zuständige kantonale Behörde einer Erweiterung der offenen Gartenterrasse sowie dem Anbau von zwei offenen Balkonen zu, gestützt auf die Besitzstandsregel von aArt. 24 Abs. 2 des Raumplanungsgesetzes (RPG; SR 700). Das Hotel wurde in den 1980er Jahren vorübergehend (ohne bauliche Änderungen) von der Gemeinde als Asylunterkunft genutzt.
2004 erwarb die B._ AG die Parzelle Nr. 125 und führte den Hotel- und Restaurantkomplex unter dem Namen "Hotel C._" weiter. Im Rahmen der Fusion der B._ AG mit der A._ AG ging das Eigentum am 28. Mai 2014 auf letztere über.
B.
Mit Gesuch vom 17. Februar 2014 beantragte die A._ AG die Bewilligung für den Bau eines dreistöckigen Gebäudes auf Parzelle 125 mit 16 bewirtschafteten Zweitwohnungen im Stockwerkeigentum, einem Restaurationsbetrieb sowie einer Tiefgarage (Projekt "D._ Lodge"). Der Grundriss des Projekts orientiert sich am bestehenden Gebäude, mit einer Erweiterung des Gebäudevolumens auf der Nord- und der Südseite; dadurch soll die zonenwidrig genutzte Fläche um rund 30 % nach aussen auf 2'264 m2erweitert werden. Die Zufahrt von der Kantonsstrasse zur Tiefgarageneinfahrt soll über die Parzelle 124 erfolgen.
Die Gesuchstellerin reichte ein Gutachten betreffend bewirtschaftete Zweitwohnungen der Schweizerischen Gesellschaft für Hotelkredit (SGH-Gutachten) vom 16. Oktober 2013 nach. Mit Schreiben vom 18. November 2014 beantragte sie gewisse Projektergänzungen und reichte weitere Unterlagen ein (Energienachweis, hydrogeologisches Gutachten; Bewilligung des Tiefbauamtes Graubünden vom 9. Oktober 2014 zum Bau der Zufahrt von der Kantonsstrasse auf Parzelle 125 über Parzelle 124).
Gegen das Vorhaben erhob der Verein Pro Natura, Schweizerischer Bund für Naturschutz (nachfolgend: Pro Natura), Einwände und beantragte, das Vorhaben nicht oder nur unter Auflagen zu bewilligen.
C.
Mit Gesamtentscheid vom 2. April 2015 erteilte das kantonale Amt für Raumentwicklung (ARE/GR) die Bewilligung zum Bauen ausserhalb des Baugebiets (BAB) gestützt auf Art. 37a RPG und Art. 43 der Raumplanungsverordnung vom 28. Juni 2000 (RPV; SR 700.1) mit Auflagen zur Zweitwohnungsnutzung und zum Landschaftsschutz. Gleichzeitig wurden die Bewilligungen zur Erstellung von Bauten in besonders gefährdeten Bereichen und zum Anschluss an die Kantonsstrasse erteilt. Das zuständige Grundbuchamt wurde angewiesen, die Auflagen betreffend Zweitwohnungsbau unter dem Stichwort "qualifizierte touristisch bewirtschaftete Wohnung" als öffentlich-rechtliche Eigentumsbeschränkung auf Parzelle 125 anzumerken.
Am 26. Juni 2015 erteilte die damalige Gemeinde Mundaun dem Bauvorhaben die Bewilligung unter Bedingungen und Auflagen und eröffnete diese zusammen mit den kantonalen Entscheiden.
D.
Am 1. September 2015 erhob Pro Natura gegen die kommunale Baubewilligung sowie den BAB-Gesamtentscheid Beschwerde beim Verwaltungsgericht des Kantons Graubünden. Dieses wies die Beschwerde am 12. April 2016 ab.
E.
Dagegen hat Pro Natura am 22. August 2016 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Er beantragt, der angefochtene Entscheid sei aufzuheben und es sei die nachgesuchte Baubewilligung für einen Neubau auf den Parzellen 124 und 125 zu verweigern.
F.
Die A._ AG und das Verwaltungsgericht beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Die Gemeinde Obersaxen Mundaun und das ARE/GR schliessen auf Abweisung der Beschwerde.
Das Bundesamt für Raumentwicklung (ARE) kommt in seiner Vernehmlassung zum Ergebnis, es handle sich um einen Wiederaufbau, weshalb die vom Verwaltungsgericht bestätigte Baubewilligung auf der Basis von Art. 37a RPG und <ref-law> aufzuheben und die Sache an die Vorinstanzen zurückzuweisen sei zur Prüfung, ob allenfalls die Voraussetzungen für eine Bewilligung nach Art. 24c RPG und <ref-law> erfüllt seien oder mit geringfügigen Projektänderungen eingehalten werden könnten.
G.
Im weiteren Schriftenwechsel halten die Beteiligten an ihren Anträgen fest, soweit sie sich noch äussern.
H.
Mit Verfügung vom 14. September 2016 wurde der Beschwerde aufschiebende Wirkung zuerkannt.

Erwägungen:
1.
Gegen den kantonal letztinstanzlichen Endentscheid des Verwaltungsgerichts steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht offen (Art. 82 lit. a, 86 Abs. 1 lit. d und 90 BGG). Der Beschwerdeführer ist als gesamtschweizerisch tätige Natur- und Heimatschutzorganisation zur Beschwerde berechtigt (Art. 12 des Bundesgesetzes vom 1. Juli 1966 über den Natur- und Heimatschutz [NHG; SR 451] i.V.m. Art. 1 und Ziff. 6 des Anhangs der Verordnung vom 27. Juni 1990 über die Bezeichnung der im Bereich des Umweltschutzes sowie des Natur- und Heimatschutzes beschwerdeberechtigten Organisationen [VBO; SR 814.076], da die Erteilung von Bewilligungen für das Bauen ausserhalb der Bauzone eine Bundesaufgabe nach <ref-law> darstellt (grundlegend <ref-ruling> E. 2 und 3 S. 71 ff.; ständige Rechtsprechung). Auf die Beschwerde ist daher einzutreten.
Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht kann insbesondere die Verletzung von Bundesrecht - einschliesslich Überschreitung oder Missbrauch des Ermessens - gerügt werden (<ref-law>). Das Bundesgericht wendet das Bundesrecht (mit Ausnahme der Grundrechte) von Amtes wegen an (<ref-law>). Es ist daher nicht an die Begründung der Parteien gebunden, sondern kann die Beschwerde auch aus andern als den geltend gemachten Gründen gutheissen oder den Entscheid mit einer Begründung bestätigen, die von jener der Vorinstanz abweicht (<ref-ruling> E. 1.4.1 S. 254 mit Hinweis).
2.
Art. 37a RPG und <ref-law> enthalten spezielle Regelungen für den Bestandesschutz von altrechtlichen gewerblichen Bauten und Anlagen in der Landwirtschaftszone. Diese gehen in ihrem Anwendungsbereich den allgemeinen Bestimmungen nach Art. 24c RPG und <ref-law> vor und sind deshalb vorab zu prüfen.
2.1. Gemäss Art. 37a RPG regelt der Bundesrat, unter welchen Voraussetzungen Zweckänderungen gewerblich genutzter Bauten und Anlagen zulässig sind, die vor dem 1. Januar 1980 erstellt wurden oder seither als Folge von Änderungen der Nutzungspläne zonenwidrig geworden sind. Diesem Auftrag ist der Bundesrat in <ref-law> nachgekommen.
<ref-law> bestimmt, dass Zweckänderungen und Erweiterungen von zonenwidrig gewordenen gewerblichen Bauten und Anlagen bewilligt werden können, wenn die Baute oder Anlage rechtmässig erstellt oder geändert worden ist (lit. a), keine wesentlichen neuen Auswirkungen auf Raum und Umwelt entstehen (lit. b) und die neue Nutzung nach keinem anderen Bundeserlass unzulässig ist (lit. c). Die zonenwidrig genutzte Fläche darf um 30 % erweitert werden; Erweiterungen innerhalb des bestehenden Gebäudevolumens werden nur zur Hälfte angerechnet (Abs. 2). Soll die zonenwidrig genutzte Fläche ausserhalb des bestehenden Gebäudevolumens um mehr als 100 m2erweitert werden, so darf dies nur dann bewilligt werden, wenn die Erweiterung für die Fortführung des Betriebs erforderlich ist (Abs. 3).
2.2. <ref-law> umfasst nach seinem klaren Wortlaut nur Zweckänderungen und Erweiterungen; dagegen sind Wiederaufbauten nach dem Grundtatbestand von Art. 24c RPG und <ref-law> zu beurteilen (Urteil 1A.289/2004 vom 7. Juni 2005 E. 2.5; Erläuterungen des Bundesamtes für Raumentwicklung zur Raumplanungsverordnung und Empfehlungen zum Vollzug, Bern 2000/01, Ziff. 2.4.5 S. 47 [nachfolgend: Erläuterungen]). Dies entspricht auch der einhelligen Lehre (WALDMANN/HÄNNI, Handkommentar RPG, Rz. 3 zu Art. 37a; RUDOLF MUGGLI, in: Aemisegger/Kuttler/Moor/Ruch (Hrsg.), Kommentar zum Bundesgesetz über die Raumplanung, Zürich 2009, Art. 37a N. 10; ULRICH ZIMMERLI, Zu den Neuerungen im Raumplanungsrecht, recht 2001 S. 97; PETER HÄNNI, Planungs-, Bau- und besonderes Umweltschutzrecht, 5. Auflage, Bern 2008, S. 207 Fn. 682; BALTHASAR HEER, St. Gallisches Bau- und Planungsrecht, Bern 2003, Rz. 485 S. 147, FRITZSCHE/BÖSCH/WIPF, Zürcher Planungs- und Baurecht, 5. Aufl., 2011, Bd. II, Ziff. 21.4.5.5 S. 1187; SAMUEL KISSLING, Stichworte zum Bauen ausserhalb der Bauzonen, Raum und Umwelt 6/2013 S. 43; ALIG/HOFFMANN, in: Griffel/Liniger/Rausch/Thurnherr (Hrsg.), Fachhandbuch Öffentliches Baurecht, 2016, Rz. 3.228).
Die Anforderungen an eine Ersatzbaute, einschliesslich deren zulässige Grösse, richten sich daher nach Art. 24c RPG und <ref-law>. Dies steht (anders als die Beschwerdegegnerin vorbringt) auch nicht im Widerspruch zu den Erläuterungen des ARE (S. 19) zur gestaffelten Anwendung von <ref-law> und Art. 24c RPG: Diese schliessen eine Kumulation des Wiederaufbaus (nach Art. 24c RPG) und der vollständigen Umnutzung bzw. Erweiterung nach <ref-law> gerade aus, kann doch ein nach <ref-law> umgenutztes bzw. erweitertes Gebäude nur wiederaufgebaut werden, soweit dies nach Art. 24c RPG und <ref-law> möglich ist; Vergleichszustand hierfür ist der Zustand im Zeitpunkt der massgeblichen Rechtsänderung (d.h. in der Regel 1972 oder 1980) und nicht der vor dem Abriss bestehende Zustand.
Entgegen der Auffassung der Beschwerdegegnerin gibt es auch keine Anhaltspunkte dafür, dass der Gesetzgeber gewerbliche Bauten hinsichtlich des Wiederaufbaus (bzw. des zulässigen Umfangs der Ersatzbaute) gegenüber anderen altrechtlichen Bauten privilegieren wollte. Art. 37a RPG erwähnt ausschliesslich Zweckänderungen, weshalb schon die Sonderregelung für Erweiterungen in <ref-law> in der Literatur teilweise als gesetzeswidrig erachtet wird (MUGGLI, a.a.O., N. 11 zu Art. 37a RPG; ALIG/HOFFMANN, a.a.O. Rn. 3.225 ff., S. 162 f.; anders das Bundesgericht im Urteil 1A.289/2004 vom 7. Juni 2005 E. 2.4 mit Hinweisen). Jedenfalls aber besteht kein Grund, <ref-law> über den in der Verordnung selbst vorgesehenen Anwendungsbereich hinaus weiter auszudehnen.
2.3. Vorliegend hielt das Verwaltungsgericht fest, dass bautechnisch gesehen ein Abbruch und ein Wiederaufbau vorliege. Es qualifizierte diesen aber in rechtlicher Hinsicht als Erweiterung und nicht als Wiederaufbau, weil die flächenmässige Erweiterung im Vordergrund stehe. Bewilligt worden sei das Resultat (Erweiterung der bestehenden Baute um höchstens 30 %) und nicht die gewählte Vorgehensweise (Abriss des bestehenden Gebäudes in einem Zug mit zeitnahem Wiederaufbau). Die bewilligte Erweiterung könne objektiv betrachtet gar nicht ohne Eingriffe in die bauliche Substanz der noch existierenden Ursprungsbaute vollzogen werden. Eine Projektrealisation in Raten wäre aus bautechnischen und ökonomischen Gründen, aber auch aus ökologischer Sicht (kein Minergie-Standard mit verbesserter Dämmung, Lüftung und umweltfreundlicher Erdwärmeheizung) eindeutig weniger sinnvoll und effizient, als die Gesamtrealisation in einem Zug.
Zwar ist dem Verwaltungsgericht zuzustimmen, dass es nicht darauf ankommen kann, ob die Arbeiten etappenweise oder in einem Zug ausgeführt werden. Entscheidend ist jedoch, dass auch im Ergebnis ein Wiederaufbau vorliegt, da (mit Ausnahme des kleinen, nur 48 m2 grossen 2. Untergeschosses) nichts von der ursprünglichen Bausubstanz bestehen bleibt. Die Baute soll im Übrigen nicht nur erweitert, sondern auch in ihrem inneren und äusseren Erscheinungsbild verändert werden (z.B. Erhöhung von Dachfirst und Raumhöhen, neue giebelständige Ausrichtung des Gebäudes, Konstruktion mit kreuzweise gestapelten Elementen, Tiefgarage). In der Begründung des Baugesuchs wurde denn auch ausgeführt, für das neue Betriebskonzept (bewirtschaftete Zweitwohnungen) sei ein Neubau erforderlich; das Bauvorhaben wurde deshalb als "Ersatzbau" bezeichnet. Es handelt sich somit um einen Wiederaufbau, der nur unter den Voraussetzungen nach Art. 24c RPG und <ref-law> zulässig ist.
2.4. Damit brauchen die übrigen Einwände des Beschwerdeführers zu Art. 37a RPG, insbesondere zum Gewerbecharakter der beabsichtigten Zweitwohnungsnutzung, nicht mehr geprüft zu werden. Offenbleiben kann auch, inwiefern das Erweiterungspotenzial bereits 1985 ausgeschöpft wurde.
3.
Zu prüfen ist, ob das Projekt nach Art. 24c RPG und Art. 41 f. RPV bewilligt werden kann.
3.1. Danach können altrechtliche Bauten und Anlagen erneuert, teilweise geändert, massvoll erweitert oder wiederaufgebaut werden (Art. 24c Abs. 1 und 2 RPG i.V.m. Art. 41 f. RPV). Veränderungen am äusseren Erscheinungsbild sind nach Art. 24c Abs. 4 RPG nur zulässig, wenn sie für eine zeitgemässe Wohnnutzung oder eine energetische Sanierung nötig oder darauf ausgerichtet sind, die Einpassung in die Landschaft zu verbessern.
<ref-law> regelt den Wiederaufbau. Danach darf eine altrechtliche Baute oder Anlage nur wieder aufgebaut werden, wenn sie im Zeitpunkt der Zerstörung oder des Abbruchs noch bestimmungsgemäss nutzbar war und an ihrer Nutzung ein ununterbrochenes Interesse besteht. Dabei darf das Gebäudevolumen massvoll erweitert werden; hierfür wird auf die Regelung für Erweiterungen in Abs. 3 verwiesen (ohne lit. a).
Eine Erweiterung gilt nach <ref-law> als massvoll, wenn die Identität der Baute oder Anlage einschliesslich ihrer Umgebung in den wesentlichen Zügen gewahrt bleibt (Abs. 1). Dies ist im Einzelfall zu prüfen (Abs. 3). Massgeblich für den Vergleich ist der Zustand, in dem sich die Baute oder Anlage im Zeitpunkt der Zuweisung zum Nichtbaugebiet befand (Abs. 2). Gemäss Abs. 3 lit. b darf die gesamte Erweiterung, sowohl bezüglich der anrechenbaren Bruttogeschossfläche als auch bezüglich der Gesamtfläche (d.h. Summe von anrechenbarer Bruttogeschossfläche und Brutto-Nebenfläche), weder 30 % noch 100 m2 überschreiten; die Erweiterungen innerhalb des bestehenden Gebäudevolumens werden nur halb angerechnet. (lit. b).
3.2. Das Verwaltungsgericht hat festgestellt, dass die bestehende, zonenwidrig genutzte Fläche von 1'742 m2 um knapp 30 % nach aussen auf 2'264 m2erweitert werde; dies entspricht den Feststellungen des ARE/GR im Gesamtentscheid vom 2. April 2015 und den Angaben in den Baugesuchsunterlagen. Damit ist die Obergrenze von 100 m2 gemäss <ref-law> um ein Mehrfaches überschritten.
3.3. Kann das Baugesuch schon aus diesem Grund nicht bewilligt werden, erübrigt sich die Prüfung der übrigen Voraussetzungen nach Art. 24c RPG (insbes. nach Abs. 4). Auch die Fragen im Zusammenhang mit der beabsichtigten Zweitwohnungsnutzung können offenbleiben.
4.
Nach dem Gesagten steht fest, dass das Projekt nicht bewilligt werden kann. Es bedarf daher keiner Rückweisung an die Vorinstanz. Vielmehr ist es Sache der Beschwerdegegnerin, allenfalls ein neues Baugesuch für ein modifiziertes Projekt einzureichen.
Die Beschwerde ist somit gutzuheissen, der angefochtene Entscheid aufzuheben und das Baugesuch der Beschwerdegegnerin vom 17. Februar 2014 abzuweisen. Damit werden alle bereits erteilten Bewilligungen (einschliesslich der Bewilligung für die Zufahrtsstrasse) hinfällig.
5.
Bei diesem Ausgang des Verfahrens wird die Beschwerdegegnerin kosten- und entschädigungspflichtig (Art. 66 und 68). Die Sache ist zur Neuverlegung der Kosten der vorinstanzlichen Verfahren an das Verwaltungsgericht zurückzuweisen.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen und der Entscheid des Verwaltungsgerichts des Kantons Graubünden, 5. Kammer, vom 12. April 2016 aufgehoben. Das Baugesuch vom 17. Februar 2014 wird abgewiesen.
2.
Die Gerichtskosten von Fr. 3'000.-- werden der Beschwerdegegnerin (A._ AG) auferlegt.
3.
Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4.
Die Sache wird zur Neuverlegung der Kosten und Entschädigungen des vorinstanzlichen Verfahrens an das Verwaltungsgericht zurückgewiesen.
5.
Dieses Urteil wird den Parteien, der Gemeinde Obersaxen Mundaun, dem Amt für Raumentwicklung Graubünden, dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, und dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 6. April 2017
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Merkli
Die Gerichtsschreiberin: Gerber