Sachverhalt: A. Mit Entscheid vom 20. August 2015 hiess das Bezirksgericht Plessur eine Klage der B._ AG (Beschwerdegegnerin) gegen A._ (Beschwerdeführerin) gut und verurteilte letztere zur Zahlung von Fr. 40'000.-- zuzüglich Zins. Dagegen erhob A._ Berufung an das Kantonsgericht von Graubünden, womit sie in der Sache verlangte, die Klage der B._ AG sei vollumfänglich abzuweisen. Am 9. Dezember 2015 forderte das Kantonsgericht A._ auf, bis zum 12. Januar 2015 einen Kostenvorschuss in Höhe von Fr. 5'000.-- zu bezahlen. Nachdem sie dieser Aufforderung nicht innert Frist nachgekommen war, setzte ihr das Kantonsgericht mit Verfügung vom 18. Januar 2016 eine Nachfrist bis zum 3. Februar 2016 an, unter Hinweis, dass für eine fristgerechte Bezahlung des Kostenvorschusses der Betrag bis zum 3. Februar 2016 zugunsten des Kantonsgerichts der Schweizerischen Post zu übergeben sei oder einem Post- oder Bankkonto in der Schweiz belastet worden sein müsse, und mit der Androhung, dass auf das Rechtsmittel nicht eingetreten würde, sollte der Vorschuss nicht innert der Nachfrist geleistet werden. In der Folge wurde der Betrag mit Valuta vom 4. Februar 2016 dem Postkonto des Kantonsgerichts gutgeschrieben. Das Kantonsgericht forderte A._ mit Schreiben vom 23. Februar 2016 auf, nachzuweisen, dass der Vorschuss spätestens am 3. Februar 2016 einem Post- oder Bankkonto in der Schweiz belastet worden sei. Innert erstreckter Frist nahm A._ schriftlich Stellung. Sie machte zusammengefasst geltend, sie habe ihrer Bank, der C._ AG in Deutschland, am 2. Februar 2016 einen Auftrag zu einer Eilüberweisung an das Kantonsgericht erteilt, mit der Anweisung, der Betrag müsse mit Valuta vom 3. Februar 2016 dem Empfänger gutgeschrieben werden. Die Verantwortung für die verspätete Gutschrift liege alleine bei der Postfinance, und die Zahlung habe daher als rechtzeitig erfolgt zu gelten. Mit Entscheid vom 19. Juli 2016 trat das Kantonsgericht auf die Berufung - wie von der B._ AG beantragt - wegen verspäteter Leistung des Kostenvorschusses in Anwendung von Art. 101 Abs. 3 ZPO nicht ein. B. A._ verlangt mit Beschwerde in Zivilsachen, der Entscheid des Kantonsgerichts sei aufzuheben, und die Sache sei "zur Neubeurteilung an die Vorinstanz zurückzuweisen". Die B._ AG beantragt, die Beschwerde abzuweisen. Die Vorinstanz begehrt ebenfalls die Abweisung der Beschwerde, soweit darauf einzutreten sei, unter Hinweis auf den angefochtenen Entscheid und Verzicht auf Gegenbemerkungen.