Sachverhalt: A. A._ erstattete am 31. Dezember 2013 Anzeige gegen seine frühere Partnerin X._ wegen Diebstahls und anderen Delikten. Er wirft ihr zusammengefasst vor, sie habe eine ihm gehörende Armbanduhr an sich genommen und verkauft. Um den Diebstahl zu vertuschen, habe X._ dann eine neue Uhr des gleichen Modells gekauft und ihm übergeben. Nach der Auflösung des gemeinsamen Haushaltes habe sie diese zweite Uhr von ihm gerichtlich zurückverlangt. B. Die Staatsanwaltschaft stellte am 30. Juni 2015 das Verfahren gegen X._ sowohl wegen des Verdachts des Diebstahls als auch für die anderen vorgeworfenen Delikte ein. Dagegen erhob A._ Beschwerde. In Bezug auf den Vorwurf des Diebstahls wies das Obergericht des Kantons Schaffhausen die Beschwerde am 20. Januar 2017 ab. C. A._ führt Beschwerde in Strafsachen. Er beantragt, der Entscheid des Obergerichts sei aufzuheben und die Sache sei zu weiteren Abklärungen und neuer Entscheidung an die Staatsanwaltschaft zurückzuweisen. D. Die Staatsanwaltschaft und X._ beantragen, die Beschwerde sei abzuweisen. Das Obergericht verzichtet auf eine Vernehmlassung.