Sachverhalt: A. Die A._ AG betreibt die B._, einen Saunabetrieb für homosexuelle Männer, wo Massagen gebucht werden können. Die entsprechenden, auf der Internetseite des Clubs dargestellten Dienstleistungen werden von Masseuren aus dem EU-/EFTA-Raum angeboten. Am 1. November 2016 führte das Amt für Wirtschaft und Arbeit des Kantons Basel-Stadt (AWA) eine Kontrolle durch. Dabei wurde festgestellt, dass die Arbeitseinsätze der Masseure dem AWA nicht gemeldet worden waren, und zwar weder als selbstständige noch als unselbstständige Erwerbstätigkeit. B. Mit Verfügung vom 16. Dezember 2016 stellte das AWA fest, dass C._ als Geschäftsführer und alleiniges Mitglied des Verwaltungsrats der A._ AG als Arbeitgeber im Sinn des Ausländerrechts einzustufen sei. Folglich sei er verpflichtet, den kurzfristigen Stellenantritt der Masseure aus den EU-/EFTA-Staaten (ohne Kroatien) gemäss Art. 9 Abs. 1bis der Verordnung vom 22. Mai 2002 über die Einführung des freien Personenverkehrs (VEP; SR 142.203) zu melden. Die Meldung habe zwingend für kurzfristige Stellenantritte ab dem 16. Januar 2017 zu erfolgen. Den gegen die Verfügung gerichteten Rekurs wies das Departement für Wirtschaft, Soziales und Umwelt (WSU) am 20. Dezember 2017 ab. Auch der Rekurs an das Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht war erfolglos (28. Oktober 2018). C. Vor Bundesgericht beantragt die A._ AG, den Entscheid des Appellationsgerichts vom 28. Oktober 2018 aufzuheben und festzustellen, dass weder die Beschwerdeführerin noch deren Geschäftsführer in Bezug auf die in der B._ tätigen Masseure als Arbeitgeber im Sinne des FZA (SR 0.142.112.681) und des Ausländerrechts einzustufen sei. Im Wesentlichen rügt sie eine unrichtige Sachverhaltsfeststellung sowie eine Verletzung von Bundesrecht (VEP, FZA, EntsG [SR 823.20]). D. Sowohl das Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht als auch das WSU beantragen vernehmlassungsweise die Abweisung der Beschwerde. Die Beschwerdeführerin hat sich dazu geäussert. Antragsgemäss hat der Präsident der II. öffentlich-rechtlichen Abteilung mit Verfügung vom 10. Januar 2019 der Beschwerde aufschiebende Wirkung erteilt.