Sachverhalt:
A.
Die Staatsanwaltschaft Basel-Stadt sprach A._ mit Strafbefehl vom 27. August 2019 des rechtswidrigen Aufenthaltes schuldig und verurteilte ihn zu einer unbedingten Freiheitsstrafe von 45 Tagen.
Der Strafbefehl wurde an A._ per Einschreiben an seinen Wohnsitz in Deutschland versandt und ihm am 12. September 2019 übergeben.
B.
A._ erhob mit undatiertem Schreiben vom 26. Dezember 2019 Einsprache gegen den Strafbefehl. Das Strafgericht des Kantons Basel-Stadt trat mit Verfügung vom 3. Januar 2020 infolge Verspätung nicht auf die Einsprache von A._ ein.
Das Appellationsgericht des Kantons Basel-Stadt wies die von A._ geführte Beschwerde mit Entscheid vom 25. März 2020 ab. Das Gesuch um unentgeltliche Verbeiständung resp. amtliche Verteidigung wies es ebenfalls ab.
C.
A._ beantragt mit Beschwerde in Strafsachen, der Entscheid des Appellationsgerichts sei aufzuheben und das Strafgericht sei anzuweisen, auf seine Einsprache gegen den Strafbefehl vom 27. August 2019 einzutreten. Zudem beantragt er, das Appellationsgericht sei anzuweisen, ihm die unentgeltliche Rechtspflege mit Rechtsanwalt Guido Ehrler als Rechtsbeistand zu bewilligen. Er ersucht um unentgeltliche Rechtspflege.
D.
Die Staatsanwaltschaft und das Appellationsgericht beantragen in ihrer Vernehmlassung, die Beschwerde sei abzuweisen.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt eine Verletzung von Art. 6 EMRK, Art. 9, Art. 29, Art. 29a und Art. 32 Abs. 3 BV sowie von <ref-law>. Mangels Übersetzung des Dispositivs habe er sich kein Bild über die ausgesprochene Strafe und damit die Tragweite des Strafbefehls machen können.
1.2.
1.2.1. Nach <ref-law> wird der beschuldigten Person, auch wenn sie verteidigt wird, in einer ihr verständlichen Sprache mindestens der wesentliche Inhalt der wichtigsten Verfahrenshandlungen mündlich oder schriftlich zur Kenntnis gebracht. Ein Anspruch auf vollständige Übersetzung aller Verfahrenshandlungen sowie der Akten besteht nicht. Bei Strafbefehlen sind nach der Rechtsprechung zumindest das Dispositiv und die Rechtsmittelbelehrung zu übersetzen (<ref-ruling> E. 1.3.3; Urteile 6B_860/2020 vom 18. November 2020 E. 1.3.2; 6B_1294/2019 vom 8. Mai 2020 E. 1.3.1; 6B_277/2019 vom 5. Juli 2019 E. 2.2.2; 6B_667/2017 vom 15. Dezember 2017 E. 5.4). Der Umfang der Beihilfen, die einer beschuldigten Person, deren Muttersprache nicht der Verfahrenssprache entspricht, zuzugestehen sind, ist nicht abstrakt, sondern aufgrund der effektiven Bedürfnisse und den konkreten Umständen des Falles zu würdigen (<ref-ruling> E. 3.1; Urteil 6B_860/2020 vom 18. November 2020 E. 1.3.2).
1.2.2. Die Beweiswürdigung der Vorinstanz kann vor Bundesgericht nur gerügt werden, wenn sie offensichtlich unrichtig bzw. willkürlich im Sinne von <ref-law> ist (<ref-law>; <ref-ruling> E. 2.3.1; <ref-ruling> E. 5.4). Die Rüge der Willkür muss in der Beschwerde explizit vorgebracht und substanziiert begründet werden (<ref-law>). Das Bundesgericht stellt insoweit hohe Anforderungen. Auf eine rein appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein (<ref-ruling> E. 1.3.1 S. 92; <ref-ruling> E. 1.1; je mit Hinweisen).
1.3. Die Vorinstanz erwägt, die Deutschkenntnisse des Beschwerdeführers seien ausreichend gewesen, um den Inhalt des Strafbefehls zu verstehen. Das Dispositiv sei mit Aufführung des Straftatbestandes, der Strafe sowie der Auferlegung der Verfahrenskosten kurz gehalten gewesen und in der Begründung sei auf die Kontrolle des Beschwerdeführers vom 28. April 2019 hingewiesen worden. Der Beschwerdeführer halte sich bereits sieben Jahre im deutschsprachigen Raum auf und sei mit dem Vorwurf der rechtswidrigen Einreise aufgrund seiner Verurteilung im Jahre 2013 vertraut. Er arbeite als Kassierer in Deutschland und es sei davon auszugehen, dass er durch den regelmässigen Kundenkontakt gewisse Sprachkenntnisse erlangt habe. Auch wenn sich der Beschwerdeführer stets der englischen Sprache bediene, würden diese Umstände darauf hinweisen, dass er die deutsche Sprache in ihren wesentlichen Grundzügen verstehe. Ferner sei dem Beschwerdeführer auf seine Frage nach den Gründen für seine Verhaftung vom Straf- und Massnahmevollzug Basel-Stadt am 5. Dezember 2019 auf Deutsch mitgeteilt worden, dass die Strafbefehle vom 8. Februar 2019 und 27. August 2019 rechtskräftig und vollziehbar seien. Der Beschwerdeführer habe daraufhin in seiner auf Englisch verfassten und am 26. Dezember 2019 zugestellten Einsprache nicht darauf hingewiesen, dass er die Strafbefehle nicht verstanden habe. Der durch den Verteidiger vor Vorinstanz erstmals vorgebrachte Einwand, der Beschwerdeführer habe den Strafbefehl aus sprachlichen Gründen nicht verstanden, müsse deswegen als Schutzbehauptung gewertet werden.
Zudem sei dem Beschwerdeführer zusammen mit dem Strafbefehl ein "Informationsblatt für fremdsprachige Personen" ausgehändigt worden, auf dem die Rechtsmittelbelehrung in diversen Sprachen, unter anderem in englischer Sprache, erteilt worden sei. Ebenfalls darauf aufgeführt worden sei, wie die Übersetzung des Strafbefehls erhältlich gemacht werden könne. Damit sei es dem Beschwerdeführer ein Leichtes gewesen, seinen Übersetzungsbedarf anzumelden, wenn er den Strafbefehl tatsächlich nicht verstanden hätte.
1.4.
1.4.1. Der Beschwerdeführer bringt vor, die Vorinstanz sei in willkürlicher Weise davon ausgegangen, dass seine Deutschkenntnisse ausreichend gewesen seien, um die Tragweite des Strafbefehls zu verstehen. Er verweist auf <ref-law>, wonach bei Personen, die keine Landessprache als Muttersprache sprechen und schreiben, für den Nachweis der Sprachkompetenzen in einer Landessprache auf die Schulbildung in einer Landessprache oder Sprachnachweise abgestellt werde. Seine Muttersprache sei nicht Deutsch und er habe auf Deutsch weder die obligatorische Schule noch eine Ausbildung auf Sekundärstufe absolviert. Ein Sprachzertifikat sei nicht aktenkundig.
Der Beschwerdeführer weist ferner darauf hin, er habe sämtliche seiner Eingaben auf Englisch verfasst und die Behörden hätten mit ihm auf Englisch kommuniziert. Das rechtliche Gehör zu seiner Wegweisungsverfügung und zur Einreisesperre sei ihm auf Englisch gewährt und das Urteil der Erstinstanz auf Englisch verfasst worden. Auch die Vorinstanz habe ihm in englischer Sprache eine Nachfrist angesetzt. Er bestreite seinen Lebensunterhalt auf Englisch und aus seinem Aufenthalt in Deutschland seit mehreren Jahren könne nicht abgeleitet werden, dass er ausreichende Sprachkenntnisse habe, um den Inhalt des Strafbefehls zu verstehen. Ferner ergebe sich auch aus seiner am 26. Dezember 2019 zugestellten Einsprache, dass er den Inhalt des Strafbefehls nicht verstanden habe. Dem Inhalt lasse sich vielmehr entnehmen, dass er davon ausgegangen sei, sich wegen nichtbezahlter Gebühren im Gefängnis zu befinden.
1.4.2. Das bisherige Verhalten des Beschwerdeführers ist im Hinblick auf die von ihm vorgebrachten Sprachkenntnisse konsistent. Er hat seine fehlenden Sprachkenntnisse kundgetan und seine Kommunikation erfolgte stets auf Englisch. Anders als im Urteil 6B_390/2020 vom 23. Juli 2020 E. 1.3.2, in welchem die ausreichenden Sprachkenntnisse der beschuldigten Person für das Verständnis eines Strafbefehls willkürfrei festgehalten wurden, konnte der Beschwerdeführer weder auf Deutsch einvernommen werden, noch hat er angegeben, keine Übersetzung zu benötigen. Dass der Beschwerdeführer den Inhalt des Strafbefehls verstanden hätte, lässt sich entgegen den vorinstanzlichen Erwägungen aus seiner am 26. Dezember 2019 zugestellten Einsprache nicht ableiten. Die von ihm geltend gemachten mangelhaften Sprachkenntnisse scheinen im Übrigen unter Berücksichtigung dessen, dass er seine Schulbildung nicht auf Deutsch absolviert hat und er soweit ersichtlich über keine Sprachnachweise verfügt, durchaus plausibel. Schliesslich hat die Vorinstanz mit ihrer zumindest teilweise auf Englisch vorgenommenen Kommunikation mit dem Beschwerdeführer zum Ausdruck gebracht, dass auch sie von seinen fehlenden Deutschkenntnissen ausging.
Für die fehlenden Deutschkenntnisse des Beschwerdeführers liegen massgebende Anhaltspunkte vor. Vor diesem Hintergrund ist es nicht nachvollziehbar, wenn die Vorinstanz die fehlenden Deutschkenntnisse lediglich mit dem Verweis auf seinen mehrjährigen Aufenthalt in Deutschland sowie seine Tätigkeit als Kassierer verneint. Indem die Vorinstanz die nicht ausreichenden Deutschkenntnisse des Beschwerdeführers als Schutzbehauptung qualifiziert hat, verfällt sie in Willkür.
Aus verfahrensökonomischen Gründen ist im Folgenden auf die weiteren Rügen des Beschwerdeführers einzugehen.
1.5. Der Beschwerdeführer macht geltend, entgegen den vorinstanzlichen Erwägungen vermöge die Abgabe des Informationsblattes den Anforderungen von <ref-law> nicht zu genügen. Eine Übersetzung des Dispositivs des Strafbefehls lag nicht vor. Das Bundesgericht hat festgehalten, dass die blosse Beilage eines Merkblattes mit Informationen allgemeiner Natur zum Strafbefehlsverfahren und Hinweise auf eine "Übersetzungshilfe" den Anforderungen von <ref-law> nicht genügen, zumal damit keine Übersetzung des im konkreten Fall gefällten Dispositivs erfolgt (Urteil 6B_1294/2019 vom 8. Mai 2020 E. 1.3.1). Entgegen den Erwägungen der Vorinstanz genügt es demnach nicht, bei nicht ausreichenden Sprachkenntnissen dem Strafbefehl ein derartiges Informationsblatt beizulegen. Indem die Vorinstanz die Verletzung von <ref-law> mit Hinweis auf das dem Strafbefehl beigelegten "Informationsblatt für fremdsprachige Personen" verneint, verletzt sie Bundesrecht.
Vor diesem Hintergrund erübrigt es sich, die vom Beschwerdeführer vorgebrachte Rüge, die Vorinstanz sei in willkürlicher Art und Weise davon ausgegangen, dass das Informationsblatt dem Strafbefehl beigelegt gewesen sei, zu prüfen.
1.6. Die bundesgerichtliche Rechtsprechung, wonach einer Partei bei einer unrichtigen Rechtsmittelbelehrung unter Vorbehalt einer groben prozessualen Unsorgfalt keine Nachteile erwachsen dürfen, kommt auch dann zur Anwendung, wenn das Dispositiv oder die Rechtsmittelbelehrung in Missachtung von <ref-law> nicht übersetzt wurde (Urteile 6B_1294/2019 vom 8. Mai 2020 E. 1.3.2; 6B_667/2017 vom 15. Dezember 2017 E. 5.4; je mit Hinweisen). Nur die Übersetzung des Dispositivs erlaubt es der beschuldigten Person, die Tragweite der mit dem Strafbefehl ausgesprochenen Sanktion und die Notwendigkeit einer Einsprache einzuschätzen (Urteil 6B_1294/2019 vom 8. Mai 2020 E. 1.3.2).
Dass dem Beschwerdeführer eine grobe prozessuale Unsorgfalt vorzuwerfen wäre, lässt sich den Erwägungen der Vorinstanz nicht entnehmen. Eine grobe prozessuale Unsorgfalt liegt nicht bereits dann vor, wenn sich die beschuldigte Person trotz dem auf einem Merkblatt enthaltenen Hinweis auf eine "Übersetzungshilfe" nicht telefonisch bei den Behörden meldet (vgl. Urteil 6B_1294/2019 vom 8. Mai 2020 E. 1.3.1 f.). Demnach verletzt die Vorinstanz Bundesrecht, wenn sie auf die Einsprache des Beschwerdeführers infolge Verspätung nicht eintritt.
2.
Der Beschwerdeführer beanstandet, dass die Vorinstanz ihm die unentgeltliche Rechtspflege wegen der Aussichtslosigkeit seiner Beschwerde verweigert hat. Angesichts des vorliegenden Verfahrensausgangs wird die Vorinstanz eine Neuregelung der Kosten - und Entschädigungsfolgen vornehmen, weswegen es sich erübrigt, auf das Vorbringen des Beschwerdeführers einzugehen.
3.
Die Beschwerde ist gutzuheissen, soweit darauf eingetreten werden kann. Bei diesem Verfahrensausgang sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Der Kanton Basel-Stadt hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 1 und 2 BGG), womit dessen Gesuch um unentgeltliche Rechtspflege gegenstandslos wird. Die Entschädigung ist praxisgemäss seinem Rechtsvertreter auszurichten.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist. Das Urteil des Obergerichts des Kantons Basel-Stadt vom 25. März 2020 wird aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Basel-Stadt hat dem Rechtsvertreter des Beschwerdeführers, Rechtsanwalt Guido Ehrler, für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 3'000.-- zu bezahlen.
4.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Einzelgericht, schriftlich mitgeteilt.
Lausanne, 19. April 2021
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Jacquemoud-Rossari
Die Gerichtsschreiberin: Bianchi