Sachverhalt: A. Die Staatsanwaltschaft des Kantons Basel-Stadt sprach X._ mit Strafbefehl vom 20. November 2018 des Fahrens ohne Fahrzeugausweis oder Kontrollschilder, des Fahrens ohne Haftpflichtversicherung sowie des Missbrauchs von Ausweisen und/oder Kontrollschildern schuldig. Sie auferlegte ihm eine bedingte Geldstrafe von 30 Tagessätzen zu Fr. 40.-- bei einer Probezeit von zwei Jahren sowie eine Busse von Fr. 1'000.-- als Zusatzstrafe zu einem Urteil aus dem Jahre 2018. Der Strafbefehl wurde mit eingeschriebener Postsendung versandt, innert Abholfrist bis zum 28. November 2018 aber nicht abgeholt. Gegen den Strafbefehl erhob X._ am 5. Februar 2019 beim Strafgericht Basel-Stadt Einsprache. Auf diese trat das Strafgericht am 15. Februar 2019 nicht ein. Die dagegen von X._ erhobene Beschwerde wies das Appellationsgericht des Kantons Basel-Stadt am 2. Mai 2019 ab. B. X._ führt Beschwerde in Strafsachen. Er beantragt sinngemäss, der Entscheid des Appellationsgerichts sei aufzuheben und auf seine Einsprache sei einzutreten. Zudem ersucht X._ um unentgeltliche Rechtspflege. C. Die Staatsanwaltschaft des Kantons Basel-Stadt beantragt die Abweisung der Beschwerde. Das Appellationsgericht des Kantons Basel-Stadt beantragt ebenfalls die Abweisung der Beschwerde und verzichtet im Übrigen auf eine Vernehmlassung. Der Beschwerdeführer verzichtet auf eine Replik.