Sachverhalt: A. X._ erlitt am 15. Oktober 2001 eine Verletzung am rechten Knie. Aufgrund der Arbeitsunfähigkeit, die ihm (in variablem Umfang) aufgrund des Unfalls regelmässig attestiert worden ist, bezog X._ bis Januar 2011 verschiedene Versicherungsleistungen. Die Staatsanwaltschaft wirft X._ vor, er sei in der Realität ab ca. 1. Februar 2002 in seiner angestammten Tätigkeit als Aussendienstmitarbeiter einer Versicherungsgesellschaft uneingeschränkt arbeitsfähig gewesen. Er habe die untersuchenden und behandelnden Ärzte bezüglich des Ausmasses der geltend gemachten Schmerzen und Beschwerden getäuscht und auf diese Weise unrechtmässig Leistungen der Versicherungen bezogen. Während der behaupteten Arbeitsunfähigkeit sei X._ als Karateinstruktor tätig gewesen. B. Das Kantonsgericht Schaffhausen erklärte X._ am 5. Juni 2014 des gewerbsmässigen Betrugs schuldig. Es bestrafte ihn mit einer bedingten Freiheitsstrafe von 18 Monaten. Gegen dieses Urteil erhoben X._ Berufung und die Staatsanwaltschaft Anschlussberufung. Das Obergericht des Kantons Schaffhausen bestätigte am 14. Juni 2016 den erstinstanzlichen Schuldspruch und bestrafte X._ mit einer bedingten Freiheitsstrafe von 22 Monaten. C. X._ führt Beschwerde in Strafsachen. Er beantragt, die von einer Detektei erstellten Videoaufnahmen seiner Tätigkeit als Karatelehrer seien als rechtswidrig zu erklären und aus den Akten zu verweisen. Das Urteil des Obergerichts sei aufzuheben und die Sache an dieses zurückzuweisen. Der Beschwerde sei die aufschiebende Wirkung zu erteilen; ihm sei die unentgeltliche Rechtspflege und Verbeiständung zu gewähren. D. Die Staatsanwaltschaft und das Obergericht des Kantons Schaffhausen verzichten auf eine Vernehmlassung.