Sachverhalt: A. Mit Schreiben vom 31. Oktober 2011 gelangte das Gemeindebauamt Arosa an die Baugesellschaft D._ als Eigentümerin der Parzelle Nr. 459 und an die Stockwerkeigentümergemeinschaft (StWEG) C._ als Eigentümerin der südlich daran angrenzenden Parzelle Nr. 442. Eine auf Anzeige von A.A._ und B.A._ hin durchgeführte Baukontrolle habe ergeben, dass in der Nordwestecke der Parzelle Nr. 459 ein bekiester Platz bestehe, der offenbar von den Bewohnern der C._ zum Parkieren verwendet werde. Zudem führe ein Plattenweg zur C._. Beide Anlagen seien bisher nicht bewilligt worden. Die StWEG C._ hielt in ihrem Antwortschreiben vom 17. Februar 2012 zunächst fest, auf der Parzelle Nr. 459 werde bereits seit 50 Jahren parkiert. Im Jahr 2000 sei das Recht dazu in einem Dienstbarkeitsvertrag verankert worden. Zwei Jahre später habe man die Fläche bekiest. Die StWEG stellte sich auf den Standpunkt, eine nachträgliche Baubewilligung sei nicht erforderlich; sie reichte aber trotzdem vorsorglich ein entsprechendes Gesuch ein. Die Gemeinde Arosa legte dieses öffentlich auf, worauf A.A._ und B.A._ Einsprache erhoben. Mit Entscheid vom 10. September 2012 wies die Baukommission der Gemeinde Arosa die Einsprache ab und bewilligte nachträglich die Autoabstellplätze und den Zugangsweg im bestehenden Umfang gemäss dem (revidierten) Situationsplan vom 24. Juli 2012. Das dagegen von A.A._ und B.A._ eingelegte Rechtsmittel wies der Gemeinderat am 17. Dezember 2012 ab. Daraufhin gelangten sie ans Verwaltungsgericht des Kantons Graubünden. Dieses wies ihre Beschwerde mit Urteil vom 13. Februar 2014 ebenfalls ab, soweit es darauf eintrat. B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht beantragen A.A._ und B.A._, das Urteil des Verwaltungsgerichts sowie die Entscheide des Gemeinderats und der Baukommission seien aufzuheben. Eventualiter sei die Sache zur Ergänzung und Untersuchung des Sachverhalts an die Vorinstanz zurückzuweisen. Zur Begründung machen sie geltend, die Parzelle sei für die drei Parkplätze in rechtlicher Hinsicht nicht hinreichend erschlossen, weil bestehende Dienstbarkeiten entgegenstünden. Das Verwaltungsgericht und die Beschwerdegegnerin beantragen die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Gemeinde hat auf eine Vernehmlassung verzichtet. Die Beschwerdeführer halten in ihrer Replik an ihren Anträgen und Rechtsauffassungen fest. Die Beschwerdegegnerin wie auch die Beschwerdeführer haben ein weiteres Schreiben eingereicht.