Sachverhalt: A. X._ ist Eigentümer der mit einem Wohnhaus überbauten Parzelle Nr. 417 sowie der östlich daran anschliessenden Parzelle Nr. 930 in der Gemeinde Y._, Gebiet B._. Auf der Parzelle Nr. 930 befand sich ein Stall, den X._ in eine Werkstatt mit darüberliegender Wohnung umbauen wollte. Ein entsprechendes Baugesuch vom 21. Januar 2007 wurde vom Gemeindevorstand der Gemeinde Y._ am 21. bzw. 24. August 2007 abgewiesen. Eine von X._ dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Graubünden am 13. bzw. 17. Dezember 2007 ab. B. Bereits am 1. Oktober 2007 reichte X._ ein Projektänderungsgesuch ein, welches vom Gemeindevorstand am 30. Oktober 2007 unter Auflagen bewilligt wurde. Am 21. Mai 2008 teilte die Gemeinde X._ mit, es sei festgestellt worden, dass er vom bewilligten Bauprojekt abweiche. Sie ordnete einen sofortigen Baustopp an und gab X._ Gelegenheit zur Stellungnahme. X._ bestritt, abweichend zur Bewilligung gebaut zu haben, und stellte eine ausführliche Stellungnahme in Aussicht. Am 25. Juni 2009 wurde X._ erneut zur Stellungnahme eingeladen, nachdem bis zu diesem Zeitpunkt weder eine Stellungnahme noch neue Pläne eingereicht worden waren. C. Am 27. August 2009 teilte die Gemeinde X._ mit, sie habe anlässlich einer Baukontrolle festgestellt, dass der ausgeführte Bau nicht den genehmigten Plänen gemäss Bewilligung vom 30. Oktober 2007 entspreche, sondern dem nicht genehmigten Baugesuch vom 21. Januar 2007. X._ habe bei Z._, dem Eigentümer der benachbarten Parzelle Nr. 1055, ein Näherbaurecht einzuholen. Erhalte er kein Näherbaurecht, müsse er bis zum 2. Oktober 2009 Pläne einreichen, aus denen ersichtlich sei, wie er den Bau in den rechtmässigen Zustand versetzen wolle. Die Einleitung eines Bussverfahrens wurde vorbehalten. Nachdem X._ erklärte, er sei mit diesem Vorgehen nicht einverstanden, versuchte die Gemeinde die Angelegenheit unter Einbezug von Z._ einvernehmlich zu lösen, was letztlich nicht gelang. D. Am 21. bzw. 22. September 2010 verfügte der Gemeindevorstand, X._ habe die Baute auf der Parzelle Nr. 930 auf das Mass gemäss Baubewilligung vom 30. Oktober 2007 zurückzuführen. Hierzu werde ihm eine Frist bis zum 31. Dezember 2010 gewährt. Falls er diese Frist nicht einhalte, werde die Gemeinde auf seine Kosten einen Dritten beauftragen. X._ wurden eine Busse von Fr. 1'000.-- sowie die Verfahrenskosten von insgesamt Fr. 8'027.40 auferlegt. E. Eine von X._ gegen die Verfügung des Gemeindevorstands erhobene Beschwerde wies das Verwaltungsgericht des Kantons Graubünden am 8. Februar 2011 ab. F. Gegen den Entscheid des Verwaltungsgerichts gelangt X._ mit Beschwerde vom 20. Juni 2011 ans Bundesgericht. Er beantragt die Aufhebung des angefochtenen Entscheids. Mit Verfügung vom 20. Juli 2011 hat das Bundesgericht der Beschwerde aufschiebende Wirkung beigelegt. G. Die Vorinstanz beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Die Gemeinde Y._ beantragt die Abweisung der Beschwerde. Z._ liess sich nicht vernehmen.