Sachverhalt: A. Am 18. August 2015 kam es zu eine Schlägerei zwischen A._ und X._. A._ stellte am 3. September 2015 Strafantrag gegen X._. B. Die Staatsanwaltschaft des Kantons Graubünden erliess am 28. Juni 2016 eine Teileinstellungsverfügung und sandte diese an die Adresse von A._ an der B._-Strasse in C._. Die Post retournierte die Sendung an die Staatsanwaltschaft mit dem Vermerk, dass der Empfänger an der angegebenen Adresse nicht habe ermittelt werden können. Daraufhin sandte die Staatsanwaltschaft am 19. Juli 2016 die Verfügung mit gewöhnlicher A-Post an die neue Adresse von A._ an der D._-Strasse in C._. C. A._ stellte am 26. Juli 2016 bei der Staatsanwaltschaft ein Gesuch um Wiederherstellung der Beschwerdefrist gegen die Teileinstellungsverfügung. Die Staatsanwaltschaft überwies dieses zuständigkeitshalber an das Kantonsgericht von Graubünden. Dieses verfügte am 2. September 2016, dass auf das Gesuch nicht eingetreten werde. Das Kantonsgericht erwägt zusammengefasst, dass wer ein Wiederherstellungsgesuch stellt, die versäumte Verfahrenshandlung innert 30 Tagen nachzuholen habe (Art. 94 Abs. 2 StPO). Der Beschwerdeführer habe keine Beschwerde gegen die Verfügung der Staatsanwaltschaft eingereicht, womit er die versäumte Verfahrenshandlung nicht nachgeholt habe. Auf das Wiederherstellungsgesuch sei demnach nicht einzutreten. Ob die Teileinstellungsverfügung überhaupt rechtswirksam zugestellt worden sei, könne offenbleiben. D. A._ führt Beschwerde in Strafsachen. Er beantragt, die Verfügung des Kantonsgerichts sei aufzuheben und die Frist zur Einreichung einer Beschwerde gegen die Verfügung der Staatsanwaltschaft sei wiederherzustellen. Ausserdem sei diese an das richtige Zustelldomizil zu senden. A._ ersucht um unentgeltliche Rechtspflege und Verbeiständung. E. Die Staatsanwaltschaft und das Kantonsgericht beantragen, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. A._ verzichtete auf weitergehende Bemerkungen.