Sachverhalt: A. Am 16. August 2012 erteilte der Gemeindevorstand Vals C.Y._ und D.Y._ die Baubewilligung für ein Wohnhaus auf dem Grundstück Nr. 956 im Gebiet "Leis" mit Auflagen. Gleichzeitig wies es die gegen das Bauvorhaben erhobene Einsprache von A.X._ und B.X._ im Sinne der Erwägungen ab. Die Gemeinde führte aus, das Gebiet "Leis" sei eine autofreie Zone; die Grundeigentümer parkierten auf einer von der Gemeinde zur Verfügung gestellten Parkzone ausserhalb des Gebiets. Allerdings müssten die Baugesuchsteller die Möglichkeit haben, zu Fuss zu ihrem Grundstück zu gelangen, damit das Grundstück als erschlossen erachtet werden könne. Der bestehende Feldweg führe über mehrere private Grundstücke. Zur Nutzung dieses Weges sei deshalb die Zustimmung der Eigentümer erforderlich, respektive müsse die Nutzung durch privatrechtliche Vereinbarungen gesichert sein. Die Baubewilligung wurde daher mit der Bedingung verknüpft, dass die Baufreigabe erst erfolge, nachdem die erforderlichen schriftlichen zivilrechtlichen Vereinbarungen vorlägen. Diese hätten sich sowohl auf ein Fusswegrecht als auch auf ein Fahrwegrecht für die Bauphase und den Gebäudeunterhalt zu beziehen. Die Baubewilligung erlösche, wenn die geforderten Vereinbarungen nicht innert eines Jahres seit Rechtskraft der Verfügung eingereicht werden. B. Gegen den Einspracheentscheid sowie die Baubewilligung erhoben A.X._ und B.X._ am 24. September 2012 Beschwerde beim Verwaltungsgericht des Kantons Graubünden mit der Begründung, es liege keine genügende strassenmässige Erschliessung des Baugrundstücks vor. Das Verwaltungsgericht bejahte eine rechtsgenügliche Erschliessung und wies die Beschwerde am 27. November 2012 ab. C. Dagegen haben A.X._ und B.X._ am 28. Januar 2013 Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht erhoben. Sie beantragen, der angefochtene Entscheid und die Baubewilligung seien aufzuheben und das Baugesuch abzuweisen. In ihrer Beschwerdebegründung berufen sie sich erstmals auf die Verletzung von Art. 75b BV und Art. 197 Ziff. 9 Abs. 2 BV. D. C.Y._ und D.Y._ (im Folgenden: die Beschwerdegegner) sowie die Gemeinde Vals schliessen auf Abweisung der Beschwerde. Das Verwaltungsgericht beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Die Beschwerdegegner machen geltend, dass die Zweitwohnungsnutzung weder im Einspracheverfahren noch vor Verwaltungsgericht thematisiert worden sei. Das Vorbringen, das Bauvorhaben verstosse gegen Art. 75b BV, sei daher ein unzulässiges Novum (Art. 99 BGG). Die Baubewilligung sei in diesem Punkt nicht angefochten und damit rechtskräftig geworden. Für den Fall, dass das Bundesgericht dennoch auf diese Rüge eintreten sollte, beantragen die Beschwerdegegner eventualiter, die Baubewilligung sei zu bestätigen und das Grundbuchamt Vals sei gestützt auf Art. 6 der Verordnung über Zweitwohnungen vom 22. August 2012 (SR 702) anzuweisen, auf dem Grundbuchblatt des Grundstücks Nr. 956 die Anmerkung "Erstwohnung" oder "bewirtschaftete Zweitwohnung" einzutragen. E. Mit Verfügung vom 20. Februar 2013 wurde das Gesuch um Gewährung der aufschiebenden Wirkung abgewiesen.