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.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt, er sei wegen eines Missverständnisses zu einer Busse von Fr. 1'000.-- verurteilt worden. Die eingeschriebene Postsendung der Staatsanwaltschaft sei elf Monate nach dem Vorfall versandt worden. Da er nicht am Wohnort anwesend gewesen sei, sei die Sendung zurück an die Staatsanwaltschaft gegangen. Die Bestimmung, wonach nicht abgeholte Einschreiben als zugestellt gelten, nehme der beschuldigten Person die Möglichkeit, gegen den Entscheid Beschwerde zu erheben und eine Aussage vor Gericht zu tätigen.
1.2. Die Vorinstanz verweist auf <ref-law>. Sie erwägt, der Beschwerdeführer sei am 18. Dezember 2017 ausreichend über die gegen ihn im Raum stehenden Vorwürfe informiert worden, weshalb er mit einer Verzeigung habe rechnen müssen. Nachdem der Zeitraum zwischen Verzeigung und Erlass des Strafbefehls etwa elf Monate betragen habe, sei die Zustellfiktion nach der bundesgerichtlichen Rechtsprechung zu bejahen. Zudem habe der Beschwerdeführer in seiner Einsprache vom 5. Februar 2019 einzig behauptet, den Strafbefehl nicht erhalten zu haben. Gründe, die ihn an der Abholung gehindert hätten, habe er nicht geltend gemacht (Entscheid S. 3 f.).
1.3. Im vorinstanzlichen Verfahren brachte der Beschwerdeführer vor, in der besagten Zeit der Zustellung abwesend gewesen zu sein (vgl. vorinstanzliche Akten Urk. 4). Davon ist auszugehen, nachdem die Vorinstanz nichts Gegenteiliges feststellt. Insbesondere stellt sie nicht fest, dass der Beschwerdeführer an seinem Zustellungsdomizil anwesend war und die Abholfrist aus Versehen oder willentlich verstreichen liess. Gründe für die Ortsabwesenheit sind in diesem Zusammenhang nicht relevant. Deshalb kann dahingestellt bleiben, ob die präzisierende Behauptung des Beschwerdeführers vor Bundesgericht, wegen Ferien abwesend gewesen zu sein, zulässig ist (vgl. <ref-law>).
1.4. Fristen, die durch eine Mitteilung oder den Eintritt eines Ereignisses ausgelöst werden, beginnen gemäss <ref-law> am folgenden Tag zu laufen. Nach <ref-law> gilt eine eingeschriebene Postsendung, die nicht abgeholt worden ist, am siebten Tag nach dem erfolglosen Zustellungsversuch als zugestellt, sofern die Person mit einer Zustellung rechnen musste.
1.4.1. Bei eingeschriebenen Postsendungen gilt eine widerlegbare Vermutung, dass der Postangestellte den Avis ordnungsgemäss in den Briefkasten oder in das Postfach des Empfängers gelegt hat und das Zustellungsdatum korrekt registriert worden ist. Es findet eine Umkehr der Beweislast in dem Sinne statt, als bei Beweislosigkeit der Entscheid zu Ungunsten des Empfängers ausfällt, der den Erhalt der Abholungseinladung bestreitet. Diese Vermutung kann durch den Gegenbeweis umgestossen werden. Sie gilt so lange, als der Empfänger nicht den Nachweis einer überwiegenden Wahrscheinlichkeit von Fehlern bei der Zustellung erbringt. Verlangt wird, dass konkrete Anzeichen für einen Fehler vorhanden sind (<ref-ruling> E. 2.3 S. 204 f.; <ref-ruling> E. 2.4.1 S. 604; je mit Hinweisen).
Solche Anzeichen sind hier nicht gegeben. Nach den vorinstanzlichen Sachverhaltsfeststellungen wurde der Strafbefehl vom 20. November 2018 eingeschrieben an jene Adresse des Beschwerdeführers verschickt, die er auch in seiner Eingabe an das Bundesgericht bezeichnet hat. Der Beschwerdeführer holte die Postsendung innert Frist bis zum 28. November 2018 nicht ab, weshalb diese am 6. Dezember 2018 wieder bei der Staatsanwaltschaft eintraf. Damit geht die Vorinstanz im Ergebnis davon aus, dass die Abholungseinladung im Sinne der oben genannten Vermutung ordnungsgemäss im Briefkasten des Beschwerdeführers deponiert wurde. Dass und weshalb ausnahmsweise nicht vom Erhalt der Abholungseinladung ausgegangen werden kann und die Feststellung der Vorinstanz willkürlich sein sollte, legt der Beschwerdeführer nicht dar.
1.4.2. Die Zustellfiktion gilt laut Gesetzestext, soweit der Adressat mit einer Zustellung rechnen musste (<ref-law>). Die Begründung eines Prozessrechtsverhältnisses verpflichtet die Parteien, sich nach Treu und Glauben zu verhalten und unter anderem dafür zu sorgen, dass ihnen behördliche Akten zugestellt werden können, welche das Verfahren betreffen (<ref-ruling> E. 3.1 S. 431 f.; <ref-ruling> E. 3.1 S. 227 f.; Urteil 6B_110/2016 vom 27. Juli 2016 E. 1.2, nicht publ. in: <ref-ruling>; je mit Hinweisen). Von einer verfahrensbeteiligten Person wird namentlich verlangt, dass sie für die Nachsendung ihrer an die bisherige Adresse gelangenden Korrespondenz besorgt ist und sie der Behörde gegebenenfalls längere Ortsabwesenheiten mitteilt oder eine Stellvertretung ernennt (<ref-ruling> E. 1.1 S. 230 mit Hinweisen).
Nach den vorinstanzlichen Feststellungen wurde der Beschwerdeführer "anlässlich der Fusspatrouille am 18. Dezember 2017 ausreichend über die gegen ihn im Raum stehenden Vorwürfe informiert" (Entscheid S. 3). Aus einem Rapport der Kantonspolizei vom 5. Januar 2018 geht hervor, dass dem Beschwerdeführer damals eine Postsendung wegen einer Verzeigung in Aussicht gestellt wurde (erstinstanzliche Akten pag. 29). Wenngleich dies noch kein Untersuchungsverfahren der Staatsanwaltschaft bedeutete, lässt es das Bundesgericht für ein Prozessrechtsverhältnis genügen, wenn dem Betroffenen von der Polizei Vorhalte gemacht werden und ihm die Eröffnung eines Vorverfahrens mitgeteilt wird (Urteil 6B_401/2019 vom 1. Juli 2019 E. 2.5 mit Hinweisen).
1.4.3. Die genannte Obliegenheit dauert nicht unbeschränkt. Das Bundesgericht hat hinsichtlich der gebotenen Aufmerksamkeitsdauer verschiedentlich einen Zeitraum bis zu einem Jahr seit der letzten verfahrensrechtlichen Handlung der Behörde als vertretbar bezeichnet. Liegt der letzte Kontakt mit der Behörde indessen längere Zeit zurück, kann von einer Zustellfiktion nicht mehr ausgegangen werden, sondern nur noch von einer Empfangspflicht des am Verfahren Beteiligten in dem Sinne, dass dieser für die Behörde erreichbar sein muss und er Adressänderungen und länger dauernde Abwesenheiten der Behörde meldet. Hingegen kann ihm eine Abwesenheit von wenigen Wochen nicht mehr entgegengehalten werden. Die Regeln über die Zustellfiktion sind in diesem Sinne vernünftig zu handhaben (Urteil 2P.120/2005 vom 23. März 2006 E. 4.2). Eine Zeitspanne bis zu einem Jahr ist aber nicht von vornherein und losgelöst von den konkreten Umständen gerechtfertigt. Als vertretbar bezeichnete das Bundesgericht etwa einen Zeitraum von neun Monaten zwischen der polizeilichen Befragung eines Strafklägers und der Zustellung einer Einstellungsverfügung. Das Bundesgericht hielt fest, der Strafkläger habe das Verfahren eingeleitet und sei daran aktiv beteiligt gewesen, weshalb er auch nach neun Monaten noch mit der Zustellung des Entscheids in der Sache habe rechnen müssen (Urteil 6B_511/2010 vom 13. August 2010 E. 4). Als keinesfalls lange Verfahrensdauer bezeichnete das Bundesgericht eine Zeitspanne von rund vier Monaten zwischen Strafanzeige und Zustellung einer Nichtanhandnahmeverfügung an den Anzeigeerstatter. Dieser habe aufgrund seiner Strafanzeige mit der Zustellung eines behördlichen Schriftstückes rechnen müssen (Urteil 1B_675/2011 vom 14. Dezember 2011 E. 3.2). Betreffend ein Strafbefehlsverfahren hielt das Bundesgericht in einem jüngeren Entscheid fest, es erscheine fraglich, ob eine Dauer bis zu einem Jahr seit der letzten Verfahrenshandlung noch vertretbar sei (Urteil 6B_110/2016 vom 27. Juli 2016 E. 1.2, nicht publ. in: <ref-ruling>, mit Hinweis auf CHRISTIAN DENYS, Ordonnance pénale: Questions choisies et jurisprudence récente, SJ 2016 II S. 125 ff. und 130). Das Genfer Kantonsgericht qualifizierte eine Zeitdauer von acht Monaten zwischen polizeilicher Befragung des Beschuldigten und Zustellung eines Strafbefehls als zu lange. <ref-law> gelange aufgrund der langen Untätigkeit der Staatsanwaltschaft nicht zur Anwendung (Urteil der Cour de Justice Genf vom 30. November 2017 E. 3.2 f., ACPR/825/2017, mit Verweis auf CHRISTIAN DENYS, a.a.O.).
Ob der Adressat nach Treu und Glauben mit einer Zustellung rechnen muss und ihm deshalb aus dem Prozessrechtsverhältnis fliessende Pflichten für eine ordnungsgemässe Zustellung obliegen, beurteilt sich wie ausgeführt nach den konkreten Verhältnissen. Diese stellen sich wie folgt dar. Im Anschluss an die polizeiliche Kontrolle vom 18. Dezember 2017, bei der dem Beschwerdeführer vom Polizeibeamten eine Postsendung in Aussicht gestellt worden war, folgten keine weiteren Kontaktaufnahmen. Das Verfahren wurde nicht auf Initiative des Beschwerdeführers eingeleitet. Ihm wurden keine Termine oder Fristen für Vorladungen angesetzt oder angekündigt und es wurde keinerlei Korrespondenz ausgetauscht. Dem Beschwerdeführer war damit auch nicht bekannt, ob das polizeiliche Ermittlungsverfahren zu einem Untersuchungsverfahren der Staatsanwaltschaft geführt hatte oder irgendwann führen würde. Das Prozessrechtsverhältnis zwischen Strafverfolgungsbehörden und Beschwerdeführer begründete und erschöpfte sich darin, dass der Beschwerdeführer am 18. Dezember 2017 wegen möglichen Widerhandlungen gegen das Strassenverkehrsgesetz polizeilich kontrolliert wurde. Die Frage, ob der Beschwerdeführer am 20. November 2018 und damit elf Monate nach der letzten und nach seinem Kenntnisstand einzigen verfahrensrechtlichen Handlung mit einer Zustellung rechnen musste, ist zu verneinen. Die Regeln über die Zustellfiktion sind wie ausgeführt vernünftig zu handhaben. Mit Blick auf den in tatsächlicher und rechtlicher Hinsicht nicht komplizierten Gegenstand des Vorverfahrens sowie die Untätigkeit der Behörde kann nicht erwartet werden, dass der Beschwerdeführer nahezu ein Jahr in jedem Zeitpunkt seine Erreichbarkeit sicherstellte und auch kürzere Ortsabwesenheiten der Behörde meldete, um keinen Rechtsnachteil zu erleiden. Vielmehr war von ihm nach Treu und Glauben und mit Blick auf die konkreten Umstände eine Aufmerksamkeitsdauer von rund einem halben Jahr zu verlangen. Daran ändern die zwei Vorstrafen des Beschwerdeführers aus den Jahren 2010 und 2018 nichts.
Dem Beschwerdeführer kann deshalb die fingierte Zustellung nicht entgegengehalten werden. Die eingeschriebene Postsendung der Staatsanwaltschaft Basel-Stadt mit Abholfrist bis zum 28. November 2018 ist rechtlich unbeachtlich. Die Zustellfiktion gelangt nicht zur Anwendung.
2.
Die Beschwerde ist gutzuheissen. Der Entscheid des Appellationsgerichts des Kantons Basel-Stadt vom 2. Mai 2019 ist aufzuheben und die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen. Bei diesem Ausgang des Verfahrens sind keine Gerichtskosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Das Gesuch um unentgeltliche Rechtspflege ist gegenstandslos geworden. Eine Parteientschädigung an den Beschwerdeführer ist nicht zuzusprechen, da ihm keine Kosten der Rechtsvertretung erwachsen sind und auch keine besonderen Verhältnisse, welche ausnahmsweise eine Parteientschädigung rechtfertigen könnten, geltend gemacht werden (Art. 68 Abs. 1 und 2 BGG; Art. 11 des Reglements vom 31. März 2006 über die Parteientschädigung und die Entschädigung für die amtliche Vertretung im Verfahren vor dem Bundesgericht [SR 173.110.210.3]).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Der Entscheid des Appellationsgerichts des Kantons Basel-Stadt vom 2. Mai 2019 wird aufgehoben und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Einzelgericht, schriftlich mitgeteilt.
Lausanne, 19. September 2019
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Faga