Sachverhalt: A. X._ ist seit dem 27. Mai 2008 Eigentümer der in der Landwirtschaftszone gelegenen und mit einer zweistöckigen Heubarge überbauten Parzelle Nr. 429 auf dem Gebiet der Gemeinde Maladers. Nachdem die Gemeinde im Sommer 2008 festgestellt hatte, dass X._ ohne Baubewilligung umfangreiche Arbeiten am Gebäude ausführen liess, erliess sie am 28. August 2008 und am 10. September 2008 Baueinstellungsverfügungen. Daraufhin reichte X._ im Oktober 2008 ein erstes und am 13. Juni 2009 ein zweites, abgeändertes Baugesuch ein, welches er in der Folge auf Aufforderung der Gemeinde hin mehrfach ergänzte. Das Baugesuch sah den Ausbau beider Stockwerke der Heubarge zu einem Ferien- und Wochenendhaus, die Errichtung eines zusätzlichen Kellers, den Anbau eines Holzschopfs sowie grössere Terrainveränderungen um das Gebäude herum vor. Weil die Bauarbeiten in der Zwischenzeit fortgesetzt wurden, erliess die Gemeinde am 28. August 2009 erneut eine Baueinstellungsverfügung. B. Mit Entscheid vom 18. Oktober 2010 stellte der Gemeindevorstand Maladers in Dispositiv-Ziffer 1 fest, am 14. April 1977 seien die zulässige Nutzung der Heubarge auf der Parzelle Nr. 429 rechtskräftig festgelegt und verschiedene Ausbauten nicht bewilligt worden. Überdies sei damals rechtskräftig verfügt worden, dass die Heubarge ausschliesslich landwirtschaftlichen Zwecken und insbesondere nicht Unterkunfts- und Wohnzwecken dienen dürfe. Mit Dispositiv-Ziffer 2 verweigerte der Gemeindevorstand die ersuchte Bewilligung für eine Zweckänderung der landwirtschaftlichen Heubarge in eine Wohn- bzw. Ferienhausnutzung sowie für sämtliche in Abweichung zum seinerzeit bewilligten Zustand bereits ausgeführten und weiter geplanten Arbeiten, namentlich für alle Terrainveränderungen inklusive Fäkalientank mit Leitung, den neuen Keller, den Innenausbau des Erd- und des Dachgeschosses zu Wohnzwecken, die bestehenden und neu vorgesehenen Fenster, die Solaranlage, den vorgesehenen gedeckten Holzschopf sowie die Holzverschalung mit Betonpfeilern. In Dispositiv-Ziffer 3 behielt sich der Gemeindevorstand vor, nach Rechtskraft der Verfügung eine Busse zu erteilen und die Wiederherstellung des rechtmässigen Zustands anzuordnen. Eine von X._ gegen den Entscheid des Gemeindevorstands vom 18. Oktober 2010 erhobene Beschwerde wies das Verwaltungsgericht des Kantons Graubünden am 17. Mai 2011 ab. C. Gegen das verwaltungsgerichtliche Urteil hat X._ am 10. November 2011 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Er beantragt die Aufhebung des angefochtenen Entscheids sowie der Verfügung der Gemeinde Maladers vom 18. Oktober 2010. Die Gemeinde Maladers sei anzuweisen, vor bzw. mit dem Entscheid über das Bauvorhaben über die Frage der Duldung der Wohnnutzung zu befinden. Eventualiter sei festzustellen, dass die bereits ausgeführten sowie projektierten Arbeiten nicht bewilligungspflichtig seien. D. Die Gemeinde Maladers und unter Verweis auf die Ausführungen im angefochtenen Entscheid die Vorinstanz beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das Amt für Raumentwicklung Graubünden verzichtet auf Vernehmlassung und beantragt die Abweisung der Beschwerde. Das Bundesamt für Raumentwicklung beantragt sinngemäss ebenfalls die Abweisung der Beschwerde. Mit Eingabe vom 9. März 2012 hält der Beschwerdeführer an der Beschwerde fest.