Sachverhalt:
A.
A.a. A._ (Arbeitnehmer, Kläger, Beschwerdeführer) mit Wohnsitz in Deutschland war seit dem 15. April 2013 bei der B._ AG, Basel, (Arbeitgeberin, Beklagte, Beschwerdegegnerin) angestellt. Sein Anfangsgehalt betrug monatlich Fr. 6'000.-- brutto, zuzüglich Fr. 140.-- Feiertagszulage und Fr. 70.-- Sonntagszulage.
Ab dem 1. September 2013 wurde das Gehalt auf Fr. 6'300.-- brutto erhöht.
Der Arbeitnehmer erlitt am 23. April 2014 einen Unfall, in dessen Folge er ab August 2014 vollumfänglich arbeitsunfähig geschrieben wurde.
A.b. Die Schweizerische Nationalbank teilte am 15. Januar 2015 mit, dass sie den Euro-Mindestkurs von Fr. 1.20 pro Euro aufhebe. Mit E-Mail vom gleichen Tag informierte die Arbeitgeberin den Arbeitnehmer über ihren Entschluss, alle nautischen Gehälter in Zukunft in Euro auszubezahlen. Das bisherige Gehalt in Schweizer Franken wurde zu einem Wechselkurs von 1:1.21 EUR/Fr. in Euro umgerechnet. Der Arbeitnehmer werde in den nächsten Tagen einen neuen Vertrag erhalten, in dem die Löhne und alle weiteren Beträge wie Sozialversicherungsabzüge und Zulagen in Euro ausgewiesen würden. Der neue Vertrag sehe ausserdem eine Lohnerhöhung von EUR 83.-- (Ausgleich für die Reisekostenentschädigung) und die Übernahme der An- und Abreisekosten zu Saisonbeginn und -ende durch die Arbeitgeberin vor. Der Lohn werde per Januar 2015 in Euro abgerechnet.
Die Arbeitgeberin stellte dem Arbeitnehmer den neuen Arbeitsvertrag per E-Mail vom 27. Januar 2015 zu und bat ihn, den Vertrag unterschrieben per Post zu retournieren. Der neue Arbeitsvertrag sollte rückwirkend per 1. Januar 2015 gültig sein und sah ein monatliches Bruttogehalt von EUR 5'289.--, zuzüglich EUR 116.-- Feiertagszulage und EUR 58.-- Sonntagszulage vor. Bereits ab Januar 2015 entrichtete die Arbeitgeberin den Lohn in Euro.
Mit E-Mail vom 23. März 2015 erinnerte sie den Arbeitnehmer daran, den Vertrag zu unterzeichnen und zu retournieren. Der Arbeitnehmer antwortete gleichentags per E-Mail, dass er zum neuen Arbeitsvertrag noch ein paar Kleinigkeiten geklärt haben möchte, weil im neuen Vertrag ein paar Dinge ständen, die noch geändert werden müssten.
Am 10. Juni 2015 schickte er den neuen Vertrag ohne Änderungen unterzeichnet zurück.
In der Folge kündigte der Arbeitnehmer sein Arbeitsverhältnis auf den 5. Januar 2016.
B.
B.a. Mit Klage vom 14. März 2017 beantragte der Arbeitnehmer dem Zivilgericht Basel-Stadt, die Arbeitgeberin sei zu verpflichten, ihm Fr. 9'000.-- brutto zuzüglich 5 % Zins seit dem 8. März 2016 zu bezahlen.
Die Arbeitgeberin beantragte die Abweisung der Klage.
Mit Entscheid vom 14. Dezember 2017 wies das Zivilgericht die Klage ab. Es erwog, zwischen den Parteien habe ab Januar 2015 eine gültige Vereinbarung darüber bestanden, den Lohn inskünftig nicht mehr in Schweizer Franken, sondern in Euro auszubezahlen. Diese Vereinbarung verstosse nicht gegen zwingende Bestimmungen des geltenden Arbeitsrechts. Die Vertragsänderung verstosse insbesondere nicht gegen das Verzichtsverbot nach <ref-law>; auch liege keine unzulässige Überwälzung des Betriebs- bzw. Währungsrisikos nach <ref-law> vor. Schliesslich sei durch die Lohnvereinbarung der Parteien auch Art. 9 Anhang I des Abkommens vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit (Freizügigkeitsabkommen, FZA; SR 0.142.112.681) nicht verletzt worden, soweit das Abkommen überhaupt zum Tragen komme.
B.b. Mit Entscheid vom 9. April 2019 wies das Appellationsgericht des Kantons Basel-Stadt eine vom Arbeitnehmer gegen den Entscheid des Zivilgerichts vom 14. Dezember 2017 erhobene Beschwerde ab, soweit es darauf eintrat.
Das Appellationsgericht erwog, die Lohnforderung des Arbeitnehmers ergebe sich nicht aus einer unabdingbaren Vorschrift des Gesetzes oder aus einer unabdingbaren Bestimmung eines Gesamtarbeitsvertrags. Sie sei deshalb nicht unverzichtbar im Sinne von <ref-law>. Ebenso wenig liess es den Einwand des Arbeitnehmers gelten, die Lohnanpassung verletze das Recht auf den Marktzugang nach dem Freizügigkeitsabkommen. Es führte unter anderem mit Hinweis auf die bundesgerichtliche Rechtsprechung (so insbesondere <ref-ruling> E. 5.2-5.5) aus, dass Art. 9 Abs. 1 Anhang I FZA nur dann auf einen Staatsangehörigen eines EU-Mitgliedstaats anwendbar sei, wenn er in der Schweiz Arbeitnehmer sei. Dabei ergebe sich insbesondere aus der Rechtsprechung zu Art. 45 des Vertrages über die Arbeitsweise der Europäischen Union (AEUV; ABl. C 326 vom 26. Oktober 2012 S. 47 ff.) und Art. 24 Abs. 1 Anhang I FZA, dass eine Person nur dann in der Schweiz Arbeitnehmerin sei, wenn sie ihre Erwerbstätigkeit in der Schweiz ausübe. Dass sich der Sitz ihrer Arbeitgeberin in der Schweiz befinde, genüge dazu nicht, was durch die Rechtsprechung des Bundesgerichts bestätigt werde, wonach die Anwendung des FZA ein grenzüberschreitendes Element voraussetze (Urteil 2P.130/2004 vom 1. Februar 2005 E. 3.4.3).
Der Wohnsitz des Klägers habe sich in Deutschland befunden; dass er sich in der Schweiz aufgehalten habe, behaupte er nicht. Das Zivilgericht habe zutreffend festgestellt, der Kläger habe seinen Lebensmittelpunkt nicht in der Schweiz, sondern in der EU gehabt, und seine Tätigkeit als Kapitän nicht in der Schweiz, sondern auf den Gewässern des übrigen Europa ausgeübt. Die Tatsache, dass sich der Sitz der Beklagten in der Schweiz befinde, der Arbeitsvertrag schweizerischem Recht unterstehe und die Beklagte in der Schweiz Sozialversicherungsbeiträge abgeliefert habe, hätten nicht zur Folge, dass der Kläger in der Schweiz Arbeitnehmer gewesen sei. Dasselbe gelte für die gemäss <ref-law> unzulässige neue Behauptung, die Schiffe der Beklagten seien im schweizerischen Schifffahrtsregister eingetragen. Aus dem Umstand, dass der Kläger eine Aufenthaltsbewilligung EU/EFTA gehabt habe, könne er für die Anwendbarkeit von Art. 9 Abs. 1 Anhang I FZA nichts zu seinen Gunsten ableiten; in der Bewilligung sei nämlich ausdrücklich festgehalten, dass er zur Erwerbstätigkeit in der Schweiz nicht berechtigt sei. Daraus ergebe sich, dass Art. 9 Abs. 1 Anhang I FZA im vorliegenden Fall nicht anwendbar sei, weil der Kläger nicht in der Schweiz Arbeitnehmer gewesen sei. Im Ergebnis habe das Zivilgericht somit zu Recht festgestellt, dass Art. 9 Abs. 1 Anhang I FZA im vorliegenden Fall keine Anwendung finde.
C.
Mit Beschwerde in Zivilsachen beantragt der Arbeitnehmer dem Bundesgericht, der Entscheid des Appellationsgerichts des Kantons Basel-Stadt vom 9. April 2019 sei aufzuheben und die Klage sei gutzuheissen.
Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde. Die Vorinstanz beantragt, auf die Beschwerde sei nicht einzutreten, eventualiter sei sie abzuweisen.

Erwägungen:
1.
Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-law>; <ref-ruling> E. 2.1).
1.1. Die Beschwerde betrifft eine Zivilsache (<ref-law>) und richtet sich gegen den Endentscheid (<ref-law>) eines oberen kantonalen Gerichts, das als Rechtsmittelinstanz entschieden hat (<ref-law>). Da es sich um eine arbeitsrechtliche Streitigkeit handelt, ist die Beschwerde in Zivilsachen nur zulässig, sofern der Streitwert mindestens Fr. 15'000.-- beträgt (<ref-law>). Vorliegend beträgt der Streitwert Fr. 9'000.--, womit der vorausgesetzte Mindestbetrag nicht erreicht wird.
1.2. Erreicht der Streitwert den erforderlichen Betrag nicht, ist die Beschwerde in Zivilsachen unter anderem dennoch zulässig, wenn sich eine Rechtsfrage von grundsätzlicher Bedeutung stellt (<ref-law>). Eine Rechtsfrage von grundsätzlicher Bedeutung ist nur zurückhaltend anzunehmen. Sie liegt vor, wenn ein allgemeines und dringendes Interesse besteht, dass eine umstrittene Frage höchstrichterlich geklärt wird, um eine einheitliche Anwendung und Auslegung des Bundesrechts herbeizuführen und damit eine erhebliche Rechtsunsicherheit auszuräumen (<ref-ruling> E. 1 S. 165; <ref-ruling> E. 1.2 S. 161; <ref-ruling> E. 1.1 S. 582 f.; je mit Hinweisen). Die Anwendung rechtsprechungsgemässer Prinzipien auf einen Einzelfall stellt keine Grundsatzfrage dar. Der blosse Umstand, dass die aufgeworfene Rechtsfrage noch nie entschieden wurde, genügt nicht. Es muss sich um eine Rechtsfrage handeln, deren Entscheid für die Praxis wegleitend sein kann und die von ihrem Gewicht her nach einer höchstrichterlichen Klärung ruft (<ref-ruling> E. 1.3.2 S. 428; <ref-ruling> E. 1.2.2.1 S. 21; <ref-ruling> E. 1.1.2 S. 147).
Im Rahmen ihrer Begründungspflicht hat die beschwerdeführende Partei darzutun, dass die Voraussetzung nach <ref-law> erfüllt ist (<ref-law>), ansonsten auf die Beschwerde nicht einzutreten ist (<ref-ruling> E. 2.6; <ref-ruling> E. 2.2.2.1; vgl. auch <ref-ruling> E. 1.3.2 S. 428).
1.3. Der Beschwerdeführer macht geltend, es stelle sich "die Frage nach der Anwendung der Art. 2 FZA bzw. Art. 9 Anhang I FZA auf den Sachverhalt". Es stelle eine Grundsatzfrage dar, ob sich der Beschwerdeführer unter den gegebenen Umständen auf das Freizügigkeitsabkommen berufen könne. Zudem sei nicht nur er, sondern das gesamte nautische Personal der Beschwerdegegnerin von der Umstellung einer Lohnzahlung von Fr. in Euro betroffen, so dass sich "die mit der Umstellung aufgeworfenen Rechtsfragen auch in anderen Zusammenhängen stellen [würden]". Damit zeigt er keine konkrete Rechtsfrage von grundsätzlicher Bedeutung auf, an deren höchstrichterlicher Klärung ein allgemeines und dringendes Interesse bestünde, um eine einheitliche Anwendung und Auslegung der massgebenden Bestimmungen herbeizuführen und damit eine erhebliche Rechtsunsicherheit auszuräumen.
Auch in seiner weiteren Beschwerdebegründung zeigt der Beschwerdeführer nicht auf, welche konkrete Rechtsfrage einer dringenden Klärung bedürfte, sondern führt verschiedenste tatsächliche Elemente ins Feld, die ihm Zugang zum Arbeitsmarkt in der Schweiz verschaffen sollen. Die Vorinstanz hat sich in ihrem Entscheid auf ein amtlich publiziertes (<ref-ruling> E. 5.2-5.5) und ein nicht publiziertes Urteil des Bundesgerichts (Urteil 2P.130/2004 vom 1. Februar 2005 E. 3.4.3) gestützt. Der Beschwerdeführer bringt in seiner Beschwerdebegründung vor, die diesen beiden Entscheiden zugrunde liegenden Verhältnisse seien mit denjenigen des vorliegenden Falls nicht vergleichbar, stellt sich jedoch seinerseits auf den Standpunkt, dass sich die Anwendbarkeit der fraglichen Bestimmungen des Freizügigkeitsabkommens auf die konkreten Verhältnisse aus einem Entscheid des Bundesgerichts (Urteil 9C_474/2011 vom 17. Februar 2012) ergebe. Zudem stützt er sich auf die Rechtsprechung des Gerichtshofs der Europäischen Union (EuGH) zum Schutzbereich der Arbeitnehmerfreizügigkeit und bringt unter Hinweis auf die verschiedenen Sachverhaltselemente des konkreten Falls vor, diese gerichtlich definierten Erfordernisse seien vorliegend erfüllt. Die Anwendung rechtsprechungsgemässer Prinzipien auf einen Einzelfall stellt jedoch nach bundesgerichtlicher Rechtsprechung keine Rechtsfrage von grundsätzlicher Bedeutung in Sinne von <ref-law> dar.
Die Voraussetzung nach <ref-law> ist demnach nicht erfüllt. Nach ihrem Wortlaut ( "wenn sich eine Rechtsfrage von grundsätzlicher Bedeutung stellt ") kann die Bestimmung nur greifen, wenn die Beantwortung der vorgelegten Rechtsfrage im betreffenden Verfahren unerlässlich ist, wenn also das Bundesgericht den Rechtsstreit ohne deren Beantwortung nicht beurteilen könnte (Urteile 4A_653/2017 vom 30. April 2018 E. 3; 4A_81/2008 vom 14. März 2008 E. 1.4). Es genügen zu lassen, dass sich vor Bundesgericht allenfallseine - im angefochtenen Entscheid gar nicht behandelte - Grundsatzfrage stellen könnte, falls zunächst eine Rechtsverletzung der Vorinstanz hinsichtlich einer nicht grundsätzlichen Frage festgestellt würde, wäre mit der gebotenen restriktiven Auslegung der Bestimmung nicht vereinbar. Der Beschwerdeführer vermag daher aus dem Verweis auf die im Urteil 4A_230/2018 vom 15. Januar 2019 E. 2.6 offen gelassene Frage der unmittelbaren Drittwirkung von Art. 9 Abs. 1 Anhang I FZA, die sich nur bei der Anwendbarkeit dieser Bestimmung stellt, nichts zu seinen Gunsten abzuleiten.
Auf die Beschwerde in Zivilsachen ist daher nicht einzutreten. Eine subsidiäre Verfassungsbeschwerde (<ref-law>) hat der Beschwerdeführer nicht erhoben.
2.
Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Auf die Beschwerde wird nicht eingetreten.
2.
Die Gerichtskosten von Fr. 500.-- werden dem Beschwerdeführer auferlegt.
3.
Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Dreiergericht, schriftlich mitgeteilt.
Lausanne, 26. November 2019
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Leemann