Sachverhalt: A. Am 9. Dezember 2012 suchte A._ seine Ehefrau, von der er getrennt lebte, in der ehelichen Wohnung zur Wahrnehmung seines Besuchsrechts auf. Nachdem er kurz ins Bad gegangen war, brachte er seine Tochter zur Grossmutter ins Schlafzimmer und eröffnete daraufhin das Feuer auf die Ehefrau und deren Eltern. Dabei tötete er seinen Schwiegervater mit fünf Schüssen. Die Ehefrau und deren Mutter erlitten teilweise schwere Schussverletzungen an den Beinen. Gemäss den Akten habe A._ seine Opfer zuerst gehunfähig machen wollen, um sie danach gezielt erschiessen zu können. Nur infolge Zündstörungen an seiner Pistole sei er an der Tötung der beiden Frauen gehindert worden. B. Mit Scheidungsurteil vom 9. April 2013 wurde der Ehefrau und Mutter die alleinige Sorge über die Tochter zugesprochen. Am 19. April 2013 stellte A._ bei der Kindes- und Erwachsenenschutzbehörde (KESB) den Antrag auf Gewährung eines Besuchsrechts und Errichtung einer Besuchsrechtsbeistandschaft zur Unterstützung der Kontaktaufnahme zwischen ihm und der Tochter. Mit Entscheid vom 18. September 2014 beschloss die KESB die Sistierung des Besuchsrechts für die Dauer von zwei Jahren und wies den Antrag auf Regelung des Besuchsrechts und Errichtung einer Beistandschaft ab. Gegen diesen Entscheid erhob A._ Beschwerde beim Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht. C. Mit Urteil vom 26. September 2014 verurteilte das Strafgericht des Kantons Basel-Stadt A._ wegen Mordes, mehrfach versuchten Mordes, mehrfach versuchter einfacher Körperverletzung, Sachbeschädigung, mehrfacher Drohung, Nötigung, versuchter Nötigung, Vergehens gegen das Waffengesetz sowie Übertretung des Waffengesetzes zu einer lebenslänglichen Freiheitsstrafe und einer Busse von Fr. 500.--. Dagegen erhob A._ Berufung. D. Mit Urteil vom 20. Juli 2015 wies das Verwaltungsgericht - in Fünferbesetzung und unter Mitwirkung von Richter Jeremy Stephenson - die Beschwerde von A._ gegen den Entscheid der KESB vom 18. September 2014 vollumfänglich ab. Das Gericht befand, die Etablierung eines Besuchskontakts zwischen dem Kind und seinem Vater würde derzeit die ungestörte psychische Genesung der durch die Straftat schwer traumatisierten Mutter und somit das Kindeswohl nachhaltig gefährden. E. Mit Ladungsverfügung vom 16. Februar 2016 setzte das Appellationsgericht des Kantons Basel-Stadt die Berufungsverhandlung auf den 27. April 2016 an und teilte den Parteien mit, dass an der Verhandlung unter anderem auch Richter Jeremy Stephenson mitwirken werde. Am 22. April 2016 stellte A._ gegen Appellationsrichter Jeremy Stephenson ein Ausstandsbegehren. Dieses wies das Appellationsgericht mit Entscheid vom 27. April 2016 ab, soweit es darauf eintrat. Im am gleichen Tag ergangenen Berufungsurteil (SB.2015.22) wurde der erstinstanzliche Schuldspruch vom Appellationsgericht bestätigt und das Strafmass auf eine Freiheitsstrafe von 20 Jahren sowie eine Busse von Fr. 500.-- festgesetzt. F. A._ erhebt Beschwerde in Strafsachen und beantragt in der Hauptsache, das Ausstandsgesuch sei gutzuheissen und das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 27. April (SB.2015.22) aufzuheben. Sämtliche bisherigen Verfahrenshandlungen, an denen Richter Jeremy Stephenson mitgewirkt habe, seien aufzuheben und zu wiederholen. Die Präsidentin des Appellationsgerichts und Richter Jeremy Stephenson haben Stellung genommen und beantragen die Abweisung der Beschwerde. Der Beschwerdeführer hat sich geäussert und ersucht weiterhin um Gutheissung der Beschwerde.