Sachverhalt: A. Die D._ AG reichte am 21. April 2008 bei der Landschaft Davos Gemeinde (nachfolgend Gemeinde Davos) ein Baugesuch für den Teilabbruch und den Neubau des Wohn- und Geschäftshauses auf der Parzelle Nr. 117 in Davos Platz ein. Gegen das Vorhaben erhob die Stockwerkeigentümergemeinschaft E._ Einsprache. Die Baubehörde der Gemeinde Davos wies die Einsprache am 16. September 2008 ab und erteilte die Baubewilligung. B. Gegen diesen Entscheid gelangten die Stockwerkeigentümergemeinschaft sowie sieben private Stockwerkeigentümer mit Beschwerde an das Verwaltungsgericht des Kantons Graubünden, welches die Beschwerde mit Urteil vom 28. April 2009 abwies. C. Gegen das Urteil des Verwaltungsgerichts erhoben die Stockwerkeigentümer A._, B._ und C._ am 3. September 2009 beim Bundesgericht gemeinsam Beschwerde in öffentlich-rechtlichen Angelegenheiten. Sie beantragen, der angefochtene Entscheid sei aufzuheben und die Baubewilligung zu verweigern. Eventuell sei die Sache an die Baubehörde der Gemeinde Davos zurückzuweisen. Die D._ AG, die Gemeinde Davos und unter Hinweis auf das angefochtene Urteil das Verwaltungsgericht des Kantons Graubünden schliessen auf Abweisung der Beschwerde, soweit darauf einzutreten sei. D. Im weiteren Schriftenwechsel halten die Beschwerdeführer an der Beschwerde und die Beschwerdegegnerin sowie die Gemeinde Davos an ihren Anträgen fest.