Sachverhalt: A. X._ wird vorgeworfen, seine Frau A._ mehrmals gewaltsam zu vaginalem, analem und oralem Geschlechtsverkehr gezwungen zu haben. Ebenfalls habe er sie mehrmals geschlagen, beschimpft und bedroht. B. Das Bezirksgericht Lenzburg sprach X._ am 23. August 2012 der mehrfachen Vergewaltigung, der mehrfachen sexuellen Nötigung, der mehrfachen einfachen Körperverletzung, der mehrfachen Tätlichkeiten, der mehrfachen versuchten schweren Körperverletzung, der mehrfachen Drohung und der mehrfachen Nötigung schuldig. Es bestrafte ihn mit einer Freiheitsstrafe von viereinhalb Jahren und einer Busse von Fr. 1'000.--. Im Zivilpunkt verurteilte es X._, A._ Fr. 26'407.70 zu bezahlen und verwies die Klage für weitergehende Forderungen auf den Zivilweg. Das Obergericht des Kantons Aargau stellte das Verfahren hinsichtlich des Vorwurfs der mehrfachen Tätlichkeiten ein und bestrafte X._ am 19. September 2013 mit einer Freiheitsstrafe von viereinhalb Jahren. Im Übrigen wies es die Berufung von X._ ab. Das Bundesgericht hob dieses Urteil am 6. Oktober 2014 auf und wies die Sache zu neuer Entscheidung an das Obergericht zurück (Urteil 6B_1204/2013). C. Das Obergericht fällte am 10. August 2015 ein neues Urteil. Es stellte das Verfahren hinsichtlich des Vorwurfs der mehrfachen Tätlichkeiten ein und bestrafte X._ mit einer Freiheitsstrafe von viereinhalb Jahren. Im Übrigen wies es die Berufung von X._ erneut ab. D. X._ führt Beschwerde in Strafsachen. Er beantragt, das Urteil des Obergerichts sei aufzuheben und er sei von Schuld und Strafe freizusprechen E. Das Obergericht verzichtet auf eine Vernehmlassung. Die Oberstaatsanwaltschaft des Kantons Aargau und A._ beantragen, die Beschwerde sei abzuweisen. X._ replizierte am 26. Februar 2016.