Sachverhalt: A. X._ befestigte am 12. März 2009 in Olten-Hammer eine selbstgebaute Stahlkonstruktion auf Bahnschienen, um einen Personenzug zum Entgleisen zu bringen. Die von ihm angebrachte Konstruktion wurde jedoch vom einfahrenden Regionalzug weggedrückt. Eine technische Untersuchung ergab, dass es nicht möglich war, mit der Stahlkonstruktion einen Zug zum Entgleisen zu bringen. Am 4. Januar 2011 goss X._ grossflächig rund 20 Liter Benzin im Altarbereich der St.-Ursen-Kathedrale in Solothurn aus in der Erwartung, dieses würde sich selber entzünden. Da dies nicht geschah, begab er sich erneut in die Kirche und entzündete das Benzin von Hand. Aufgrund des Feuers und der damit einhergehenden Rauchentwicklung entstand Sachschaden in Millionenhöhe. Verletzt wurde niemand. B. Am 28. September 2011 verurteilte das Amtsgericht von Solothurn-Lebern X._ aufgrund dieser und weiterer Handlungen wegen Brandstiftung, mehrfacher versuchter Störung des Eisenbahnverkehrs, Schreckung der Bevölkerung sowie Drohung zu einer Freiheitsstrafe von 14 Monaten. Gleichzeitig ordnete es eine stationäre therapeutische Massnahme nach Art. 59 StGB an. Vom Vorwurf der versuchten schweren Körperverletzung sprach es ihn frei. Das Urteil ist rechtskräftig. C. Das Amt für Justizvollzug hob die stationäre therapeutische Massnahme von X._ wegen Aussichtslosigkeit am 2. Juli 2015 auf. Auf dessen Antrag ordnete das Amtsgericht von Solothurn-Lebern am 15. Dezember 2015 die nachträgliche Verwahrung gegen X._ an. Hiergegen erhob X._ sowohl Berufung als auch Beschwerde. Das Obergericht des Kantons Solothurn trat auf die Berufung nicht ein. Es führte im Rahmen des Beschwerdeverfahrens am 11. August 2016 eine Hauptverhandlung durch und eröffnete seinen Beschluss den Parteien am 12. August 2016 mündlich. In Gutheissung der Beschwerde von X._ hob es den Nachentscheid des Amtsgerichts von Solothurn-Lebern auf und wies den Antrag des Amtes für Justizvollzug auf Anordnung einer nachträglichen Verwahrung sowie den Antrag der Staatsanwaltschaft auf Anordnung prozessualer Sicherheitshaft ab. Gleichzeitig ordnete es an, dass X._ am 17. August 2016 um 17.00 Uhr aus dem "Verwahrungsvollzug" zu entlassen sei und der Erwachsenenschutzbehörde Olten-Gösgen Mitteilung zu machen sowie eine begründete Urteilskopie zuzustellen sei. D. Die Staatsanwaltschaft des Kantons Solothurn erhob am 12. August 2016 per Fax (Posteingang: 15. August 2016) Beschwerde ans Bundesgericht und beantragt, der Entscheid des Obergerichts vom 11. August 2016 sei aufzuheben und gegen X._ sei die nachträgliche Verwahrung anzuordnen. Eventualiter sei die Sache zur Neubeurteilung an das Obergericht zurückzuweisen. X._ und das Obergericht beantragen die Abweisung der Beschwerde und der Verfahrensanträge sowie die Entlassung aus dem "Verwahrungsvollzug". X._ ersucht um unentgeltliche Rechtspflege und Verbeiständung. Der Präsident der Strafrechtlichen Abteilung des Bundesgerichts hat am 17. August 2016 verfügt, dass X._ bis zum Entscheid über das Gesuch um aufschiebende Wirkung der Beschwerde nicht aus der Haft entlassen werden darf. E. Der schriftlich begründete Entscheid des Obergerichts wurde den Parteien am 31. August 2016 eröffnet, womit die Beschwerdefrist gemäss Art. 100 Abs. 1 BGG am 30. September 2016 endete.