Sachverhalt: A. A._ (Klägerin, Beschwerdeführerin), österreichische Staatsangehörige, schloss am 21. Juni 2011 einen Arbeitsvertrag mit der C._ AG ab. Sie trat am 11. Juli 2011 mit einer ab diesem Tag gültigen Aufenthaltsbewilligung B das vereinbarte Arbeitsverhältnis als Assistentin der Geschäftsleitung an. Die C._ AG führte für ihre Angestellten bei der B._ AG (Beklagte, Beschwerdegegnerin) eine Kollektiv-Krankentaggeldversicherung nach Versicherungsvertragsgesetz. Am 31. Januar 2013 kündigte die C._ AG das Arbeitsverhältnis mit der Klägerin per 31. März 2013. Mit Formular vom 12. März 2013 teilte die C._ AG sodann der Beklagten eine Arbeitsunfähigkeit der Klägerin seit 3. Februar 2013 bis voraussichtlich 24. März 2013 infolge eines Grippeinfekts mit. Dr.med. D._, Österreich, bestätigte diese wie auch anschliessende Arbeitsunfähigkeiten. Die Beklagte erbrachte vom 6. März bis 30. April 2013 Taggelder. Am 7. März 2013 meldete sich die Klägerin definitiv von ihrem schweizerischen Aufenthaltsort in V._ nach Österreich ab. Nachdem die Beklagte hiervon Kenntnis erhalten hatte, teilte sie der Klägerin mit Schreiben vom 24. September 2013 mit, dass die Leistungspflicht per 7. März 2013 erloschen sei, da sich die Klägerin ohne schriftliche Zustimmung der Beklagten ins Ausland begeben und ihren gesetzlichen Wohnsitz nach Österreich verlegt habe. Auf eine Rückforderung der bis am 30. April 2013 erbrachten Leistungen werde aber verzichtet. B. B.a. Die Klägerin reichte am 24. September 2014 Klage beim Arbeitsgericht Zürich auf Bezahlung von Taggeldern von insgesamt Fr. 38'841.-- zuzüglich Zinsen ein. Mit Beschluss vom 6. November 2014 trat das Arbeitsgericht auf die Klage mangels sachlicher Zuständigkeit nicht ein. B.b. Die Klägerin erhob anschliessend am 3. Dezember 2014 am Sozialversicherungsgericht des Kantons Zürich Klage und beantragte, die Beklagte sei zu verpflichten, ihr Fr. 38'841.-- nebst verschiedenen Zinsbetreffnissen zu bezahlen. Mit Urteil vom 31. März 2016 wies das Sozialversicherungsgericht die Klage ab. C. Dagegen erhob die Beschwerdeführerin Beschwerde in Zivilsachen und beantragt, das Urteil des Sozialversicherungsgerichts sei aufzuheben und es sei die Beschwerdegegnerin zu verpflichten, der Beschwerdeführerin Fr. 38'841.-- zuzüglich 5 % Zinsen auf Fr. 4'961.55 seit 31.05.2013, 5 % Zinsen auf Fr. 4'801.50 seit 30.06.2013, 5 % Zinsen auf Fr. 4'961.55 seit 31.07.2013, 5 % Zinsen auf Fr. 4'801.50 seit 30.09.2013, 5 % Zinsen auf Fr. 4'961.55 seit 31.10.2013, 5 % Zinsen auf Fr. 4'801.50 seit 30.11.2013, 5 % auf Fr. 4'961.55 seit 31.12.2013 und 5 % Zinsen auf Fr. 4'961.55 seit 31.01 2014 zu bezahlen. Eventualiter sei die Sache zur Sachverhaltsergänzung und neuen Entscheidung an die Vorinstanz zurückzuweisen. Die Beschwerdegegnerin beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Die Vorinstanz verzichtete auf Vernehmlassung. Die Beschwerdeführerin reichte eine Replik ein.