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.

Erwägungen:
1.
Der Privatkläger ist zur Beschwerde gegen eine Einstellungsverfügung nur legitimiert, wenn der angefochtene Entscheid sich auf die Beurteilung seiner Zivilansprüche auswirken kann (Art. 81 Abs. 1 lit. b Ziff. 5 BGG). In erster Linie geht es um Ansprüche auf Schadenersatz und Genugtuung gemäss <ref-law>, die üblicherweise vor den Zivilgerichten geltend gemacht werden müssen. Gemäss Art. 42 Abs. 1 und 2 BGG hat der Beschwerdeführer darzulegen, dass die gesetzlichen Legitimationsvoraussetzungen erfüllt sind. Richtet sich die Beschwerde gegen die Einstellung oder Nichtanhandnahme eines Verfahrens, hat der Privatkläger nicht notwendigerweise bereits vor den kantonalen Behörden eine Zivilforderung geltend gemacht. Selbst wenn er bereits adhäsionsweise privatrechtliche Ansprüche geltend gemacht hat (vgl. <ref-law>), werden in der Einstellungsverfügung keine Zivilklagen behandelt (<ref-law>). In jedem Fall muss der Privatkläger im Verfahren vor Bundesgericht darlegen, aus welchen Gründen sich der angefochtene Entscheid inwiefern auf welche Zivilforderungen auswirken kann. Das Bundesgericht stellt an die Begründung der Legitimation strenge Anforderungen. Genügt die Beschwerde diesen Begründungsanforderungen nicht, kann darauf nur eingetreten werden, wenn aufgrund der Natur der untersuchten Straftat ohne Weiteres ersichtlich ist, um welche Zivilforderungen es geht (<ref-ruling> E. 1.1 mit Hinweisen).
Der Beschwerdeführer machte am 10. September 2014 unter anderem eine Zivilforderung in der Höhe von Fr. 47'500.-- geltend. Er führt aus, dass dies dem Verkehrswert der ihm entwendeten Uhr entspreche; in diesem Umfang verlange er Schadenersatz. Der Beschwerdeführer ist somit legitimiert, den Entscheid der Vorinstanz vor dem Bundesgericht anzufechten.
2.
2.1. Der Beschwerdeführer rügt zusammengefasst, dass die Voraussetzungen für eine Einstellung des Verfahrens nicht gegeben seien. Es bestehe ein erheblicher Verdacht, dass sich die Beschwerdegegnerin 2 des Diebstahls schuldig gemacht habe.
2.2. Die Staatsanwaltschaft verfügt die Einstellung des Verfahrens unter anderem, wenn kein Tatverdacht erhärtet ist, der eine Anklage rechtfertigt (<ref-law>) oder kein Straftatbestand erfüllt ist (<ref-law>). Der Entscheid über die Einstellung eines Verfahrens hat sich nach dem Grundsatz "in dubio pro duriore" zu richten. Dieser ergibt sich aus dem Legalitätsprinzip. Er bedeutet, dass eine Einstellung durch die Staatsanwaltschaft grundsätzlich nur bei klarer Straflosigkeit bzw. offensichtlich fehlenden Prozessvoraussetzungen angeordnet werden darf. Hingegen ist (sofern die Erledigung mit einem Strafbefehl nicht in Frage kommt) Anklage zu erheben, wenn eine Verurteilung wahrscheinlicher erscheint als ein Freispruch. Falls sich die Wahrscheinlichkeiten eines Freispruchs oder einer Verurteilung in etwa die Waage halten, drängt sich in der Regel, insbesondere bei schweren Delikten, eine Anklageerhebung auf. Bei zweifelhafter Beweis- bzw. Rechtslage hat nicht die Staatsanwaltschaft über die Stichhaltigkeit des strafrechtlichen Vorwurfs zu entscheiden, sondern das zur materiellen Beurteilung zuständige Gericht. Der Grundsatz, dass im Zweifelsfall nicht eingestellt werden darf, ist auch bei der Überprüfung von Einstellungsverfügungen zu beachten. Bei der Beurteilung dieser Frage verfügen die Staatsanwaltschaft und die Vorinstanz über einen gewissen Spielraum, den das Bundesgericht mit Zurückhaltung überprüft.
Stehen sich gegensätzliche Aussagen gegenüber ("Aussage gegen Aussage"-Situation) und ist es nicht möglich, die einzelnen Aussagen als glaubhafter oder weniger glaubhaft zu bewerten, ist nach dem Grundsatz "in dubio pro duriore" in der Regel Anklage zu erheben. Dies gilt insbesondere, wenn typische "Vier-Augen-Delikte" zu beurteilen sind, bei denen oftmals keine objektiven Beweise vorliegen. Auf eine Anklageerhebung kann verzichtet werden, wenn der Strafkläger ein widersprüchliches Aussageverhalten offenbarte und seine Aussagen daher wenig glaubhaft sind oder wenn eine Verurteilung unter Einbezug der gesamten Umstände aus anderen Gründen als von vornherein unwahrscheinlich erscheint (<ref-ruling> E. 2.2.1 und 2.2.2 mit Hinweisen).
2.3. Die Vorinstanz erwägt insbesondere, es sei abwegig anzunehmen, dass die Beschwerdegegnerin 2 Fr. 47'500.-- aufgewendet haben soll, um eine neue Uhr zu kaufen und somit den angeblichen Diebstahl zu vertuschen. Auch sei aufgrund ihrer angespannten finanziellen Situation nicht nachvollziehbar, dass sie Fr. 9'000.-- geleistet haben soll, um dem Beschwerdeführer den Kauf der ersten, angeblich gestohlenen Uhr zu ermöglichen. Im Ergebnis hält die Vorinstanz fest, dass die Aussagen der Beteiligten diametral auseinandergehen würden und sich nicht eruieren lasse, was genau vorgefallen sei, respektive, wer Recht habe. Es sei auch nicht ersichtlich, welche weiteren Beweismittel allenfalls diesbezüglich Klarheit bringen könnten. Damit könne der Beschwerdegegnerin 2 nicht mit hinreichender Wahrscheinlichkeit vorgeworfen werden, sie habe das Eigentum des Beschwerdeführers unrechtmässig verletzt. Es fehle daher an einem hineinreichenden Tatverdacht, weshalb die Staatsanwaltschaft das Verfahren zu Recht eingestellt habe (Entscheid, S. 9).
Dass die Aussagen der Beteiligten diametral auseinandergehen, genügt alleine nicht für eine Einstellung des Verfahrens. Es wäre vielmehr Aufgabe des Sachgerichts, diese Aussagen eingehend zu würdigen. Auch lassen die weiteren, von der Vorinstanz erwähnten Umstände nicht den Schluss zu, dass eine Verurteilung von vornherein unwahrscheinlich wäre. Die Rüge ist begründet.
3.
Die Beschwerde ist gutzuheissen. Die Sache ist an die Staatsanwaltschaft zur Weiterführung der Strafuntersuchung und an die Vorinstanz zur Neuregelung der Kosten- und Entschädigungsfolgen zurückzuweisen.
Für das bundesgerichtliche Verfahren sind die Kosten der unterliegenden Partei, jedoch nicht dem Kanton, aufzuerlegen (Art. 66 Abs. 1 und 4 BGG). Der Kanton Schaffhausen und die Beschwerdegegnerin 2 haben dem Beschwerdeführer eine angemessene Parteientschädigung auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Der Entscheid des Obergerichts des Kantons Schaffhausen vom 20. Januar 2017 wird aufgehoben, soweit dieser die Einstellung des Verfahrens wegen Diebstahls betrifft. Die Sache wird an die Staatsanwaltschaft des Kantons Schaffhausen zur Weiterführung der Strafuntersuchung und an die Vorinstanz zur Neuregelung der Kosten- und Entschädigungsfolgen zurückgewiesen.
2.
Der Beschwerdegegnerin 2 werden Gerichtskosten von Fr. 1'500.-- auferlegt.
3.
Die Parteientschädigung von Fr. 3'000.-- an den Beschwerdeführer tragen je zur Hälfte der Kanton Schaffhausen und die Beschwerdegegnerin 2 unter solidarischer Haftung.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Schaffhausen schriftlich mitgeteilt.
Lausanne, 1. Dezember 2017
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Moses