Sachverhalt: A. Das Kantonsgericht St. Gallen verurteilte X._, geb. 1. Februar 1957, am 21. April 1998 zweitinstanzlich wegen mehrfacher sexueller Handlungen mit Kindern und mehrfacher Pornographie zu einer Gefängnisstrafe von zweieinhalb Jahren. Gleichzeitig wurde eine ambulante psychotherapeutische Massnahme angeordnet. Am 24. Februar 2000 wurde er bedingt aus dem Strafvollzug entlassen. Das (damalige) Bezirksgericht Oberrheintal verurteilte X._ am 15. Mai 2001 erneut wegen mehrfacher sexueller Handlungen mit Kindern, mehrfacher sexueller Belästigung sowie mehrfacher Pornographie zu zwei Jahren Gefängnis. Gleichzeitig ordnete es eine ambulante Massnahme an. Das Justiz- und Polizeidepartement des Kantons St. Gallen (heute Sicherheits- und Justizdepartement [SJD]) widerrief am 2. Oktober 2001 die bedingte Entlassung vom 24. Februar 2000 und ordnete den Vollzug des noch nicht verbüssten Strafrests an. Am 20. August 2002 wies es ein Gesuch von X._ um bedingte Entlassung ab, stellte den Vollzug der ambulanten Massnahme ein und beantragte dem (damaligen) Bezirksgericht Oberrheintal, X._ zu verwahren. Dieses ordnete am 27. Mai 2003 die Verwahrung gestützt auf aArt. 43 Ziff. 1 Abs. 2 StGB an. Die dagegen erhobenen Rechtsmittel wurden abgewiesen (vgl. Urteile des Bundesgerichts 6P.110/2005 und 6S.325/2005 vom 20. Dezember 2005). Als Folge der Revision des allgemeinen Teils des Strafgesetzbuchs ordnete das Kreisgericht Rheintal am 26. Juni 2007 anstelle der altrechtlichen Verwahrung eine (neurechtliche) stationäre therapeutische Massnahme nach Art. 59 StGB an. B. Das SJD lehnte am 13. Februar 2012 das Gesuch von X._ um bedingte Entlassung aus der stationären therapeutischen Massnahme ab, hob die Massnahme auf und beantragte dem Kreisgericht, X._ zu verwahren. Gegen den Aufhebungsentscheid des SJD legte X._ bei der Anklagekammer des Kantons S t. Gallen Beschwerde ein. Diese sistierte das Beschwerdeverfahren am 18. April 2012 bis zum Vorliegen eines rechtskräftigen Entscheids über die beim Kreisgericht beantragte Verwahrung. Mit Entscheid vom 30. Mai 2012 hob das Kreisgericht die stationäre therapeutische Massnahme auf und ordnete die nachträgliche Verwahrung von X._ gestützt auf Art. 62c Abs. 4 i.V.m. Art 64 StGB an. Das Kantonsgericht bestätigte am 13. November 2013 die nachträgliche Anordnung der Verwahrung, hob den kreisgerichtlichen Entscheid aber insofern auf, als damit die stationäre therapeutische Massnahme aufgehoben worden war. Das Bundesgericht hob diesen Entscheid am 11. Februar 2015 auf (Urteil 6B_227/2014) - im Wesentlichen mit der Begründung, dass vor einem Entscheid betreffend die Verwahrung über die Frage der Aufhebung bzw. der Aussichtslosigkeit der betreffenden stationären Massnahme rechtskräftig entschieden werden müsse. C. Das Kantonsgericht wies die Sache in der Folge zu neuerlicher Entscheidung an das Kreisgericht zurück. Die Anklagekammer entschied über die bei ihr hängige (sistierte) Beschwerde betreffend Aufhebung der stationären therapeutischen Massnahme und wies diese ab. Das Kreisgericht ordnete am 2. Dezember 2015 die Verwahrung von X._ an. Gleichzeitig versetzte es ihn in Sicherheitshaft. X._erhob dagegen erneut Beschwerde, welche von der Anklagekammer am 31. März 2016 abgewiesen wurde. D. X._ erhebt Beschwerde in Strafsachen vor Bundesgericht und beantragt, den Entscheid der Anklagekammer vom 31. März 2016 aufzuheben; er sei zudem umgehend aus der Sicherheitshaft zu entlassen. Eventuell sei anstelle der Verwahrung erneut eine stationäre Massnahme anzuordnen. Ferner ersucht er für das bundesgerichtliche Verfahren um unentgeltliche Prozessführung und um Verbeiständung. E. Die Staatsanwaltschaft beantragt, die Beschwerde abzuweisen und verweist auf das angefochtene Urteil. Die Anklagekammer verzichtet unter Verweis auf das vorinstanzliche Urteil auf eine Vernehmlassung.