Sachverhalt: A. X._ befindet sich seit 1988 im Massnahmenvollzug. Er wurde gestützt auf die Urteile des Appellationsgerichts des Kantons Basel-Stadt vom 4. März 1988 und des Kantonsgerichts St. Gallen vom 21. November 1995 im Sinne von Art. 42 aStGB verwahrt. Infolge der Revision des Allgemeinen Teils des Strafgesetzbuches wurde die Verwahrung von X._ überprüft und am 8. Januar 2008 in eine stationäre Massnahme nach Art. 59 Abs. 1 und 3 StGB überführt. B. Die Vollzugsbehörde (Ressort Strafvollzug des Amtes für Justizvollzug) verweigerte am 11. Februar 2009 die bedingte Entlassung von X._. Auf den Rekurs des Betroffenen trat das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt am 11. Mai 2009 nicht ein. X._ rekurierte an den Regierungsrat des Kantons Basel-Stadt. Der Rekurs wurde dem Appellationsgericht des Kantons Basel-Stadt (als Verwaltungsgericht) am 10. Juni 2009 als Sprungrekurs überwiesen. Mit Urteil vom 16. September 2009 bestätigte dieses den Entscheid der Vollzugsbehörde vom 11. Februar 2009. X._ führt Beschwerde beim Bundesgericht. Er beantragt im Wesentlichen die Aufhebung des angefochtenen Entscheids des Appellationsgerichts. Überdies ersucht er um unentgeltliche Rechtspflege und Verbeiständung. C. Das Appellationsgericht verzichtet am 29. Januar 2010 auf eine Vernehmlassung. Das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt schliesst in seiner Eingabe vom 17. Februar 2010 auf Abweisung der Beschwerde. Die Vollzugsbehörde hat sich innert Frist nicht vernehmen lassen. 