Sachverhalt:
A.
X._ wurde mit Entscheid der Eidgenössischen Steuerverwaltung (ESTV) vom 21. August 2012 per 1. Januar 2009 der Mehrwertsteuerpflicht unterstellt. Nachdem er trotz Mahnung vom 18. Februar 2014 die Mehrwertsteuerabrechnung für das 2. Quartal 2010 nicht eingereicht hatte, leitete die ESTV mit Schlussprotokoll vom 1. April 2014 ein Verwaltungsstrafverfahren ein. Gleichzeitig stellte sie in Aussicht, dass eine Busse verhängt werde, wenn die Mehrwertsteuerabrechnung nicht innert 10 Tagen eingereicht werde. Nach unbenutztem Ablauf der Frist sprach die ESTV X._ mit Strafbescheid vom 29. April 2014 der Widerhandlung im Sinne von Art. 98 Bst. b MWSTG (SR 641.20), begangen durch Nichteinreichen der Mehrwertsteuerabrechnung für das 2. Quartal 2010 trotz vorheriger Mahnung, schuldig. Sie bestrafte ihn mit einer Busse von Fr. 500.-- und auferlegte ihm die Verfahrenskosten von Fr. 110.--. X._ erhob Einsprache gegen den Strafbescheid.
Mit Strafverfügung vom 13. Juni 2014 wies die ESTV die Einsprache ab. Sie bestätigte die ausgefällte Busse und verpflichtete X._ zur Bezahlung der Verfahrenskosten von Fr. 250.--.
X._ verlangte die gerichtliche Beurteilung (Art. 71 VStrR [SR 313.0]).
B.
Am 4. November 2014 sprach das Strafgericht Basel-Stadt X._ der fahrlässigen Verletzung von Verfahrenspflichten nach MWSTG schuldig und bestrafte ihn mit einer Busse von Fr. 500.--. Ferner auferlegte es ihm die Kosten des Verfahrens der Verwaltung von Fr. 250.-- sowie die Urteilsgebühr von Fr. 500.--.
C.
X._ erhob Berufung gegen das Urteil des Strafgerichts Basel-Stadt. Im Berufungsverfahren reichte er einen Einspracheentscheid der ESTV vom 10. November 2014 ein, welcher explizit die Befreiung von der Mehrwertsteuerpflicht für den Zeitraum vom 1. Januar bis 31. Dezember 2010 und die Löschung des Beschwerdeführers aus dem Register der Mehrwertsteuerpflichtigen per 31. Dezember 2009 festhält. Das Appellationsgericht Basel-Stadt hiess die Berufung am 27. November 2015 gut und sprach X._ von der Anklage der fahrlässigen Verletzung von Verfahrenspflichten nach MWSTG frei. Es bestätigte den erstinstanzlichen Entscheid im Kostenpunkt. Für das Berufungsverfahren wurden keine Kosten erhoben.
D.
X._ führt Beschwerde in Strafsachen und beantragt, das Urteil des Appellationsgerichts Basel-Stadt vom 27. November 2015 sei im Kostenpunkt aufzuheben und sämtliche Kosten seien dem Staat aufzuerlegen. In prozessualer Hinsicht beantragt X._ sinngemäss, der Beschwerde sei die aufschiebende Wirkung zuzuerkennen.
E.
Das Appellationsgericht Basel-Stadt und die ESTV schliessen auf Abweisung der Beschwerde. Die Staatsanwaltschaft des Kantons Basel-Stadt verzichtet auf Vernehmlassung.

Erwägungen:
1.
Der Beschwerdeführer macht geltend, aufgrund des Freispruchs dürften ihm keine Kosten auferlegt werden.
1.1. Die Kosten des gerichtlichen Verfahrens und deren Verlegung bestimmen sich, vorbehältlich Art. 78 Abs. 4 VStrR, nach den Art. 417 bis Art. 428 StPO (Art. 97 Abs. 1 VStrR). Im Urteil können die Kosten des Verfahrens der Verwaltung gleich wie die Kosten des gerichtlichen Verfahrens verlegt werden (Art. 97 Abs. 2 VStrR).
Nach Art. 426 Abs. 2 StPO können der beschuldigten Person die Verfahrenskosten ganz oder teilweise auferlegt werden, wenn sie rechtswidrig oder schuldhaft die Einleitung des Verfahrens bewirkt oder dessen Durchführung erschwert hat.
Nach der Rechtsprechung des Bundesgerichts verstösst eine Kostenauflage bei Freispruch oder Einstellung des Verfahrens gegen die Unschuldsvermutung (Art. 10 Abs. 1 StPO, Art. 32 Abs. 1 BV und Art. 6 Ziff. 2 EMRK), wenn der beschuldigten Person in der Begründung des Kostenentscheids direkt oder indirekt vorgeworfen wird, es treffe sie ein strafrechtliches Verschulden. Damit käme die Kostenauflage einer Verdachtsstrafe gleich. Dagegen ist es mit Verfassung und Konvention vereinbar, einer nicht verurteilten beschuldigten Person die Kosten zu überbinden, wenn sie in zivilrechtlich vorwerfbarer Weise eine geschriebene oder ungeschriebene Verhaltensnorm, die sich aus der Gesamtheit der schweizerischen Rechtsordnung ergeben kann, klar verletzt und dadurch das Strafverfahren veranlasst oder dessen Durchführung erschwert hat. In tatsächlicher Hinsicht darf sich die Kostenauflage nur auf unbestrittene oder bereits klar nachgewiesene Umstände stützen (<ref-ruling> E. 3b; <ref-ruling> E. 1b; <ref-ruling> E. 2a; Urteil 6B_67/2014 vom 2. September 2014 E. 2.3; je mit Hinweisen). Das Gericht muss die Kostenauflage bei Freispruch oder Einstellung begründen. Es muss darlegen, inwiefern die beschuldigte Person durch ihr Handeln in zivilrechtlich vorwerfbarer Weise gegen eine Verhaltensnorm klar verstossen hat (Urteile 6B_662/2013 vom 19. Juni 2014 E. 1.3; 1P.164/2002 vom 25. Juni 2002 E. 1.2.2, in: Pra 2002 Nr. 203 S. 1067).
1.2. Die Vorinstanz erwägt, mit der Nichtabmeldung von der Steuerpflicht gemäss Art. 14 Abs. 5 MWSTG und der mangelhaften Auskunftserteilung gemäss Art. 68 Abs. 1 MWSTG habe der Beschwerdeführer gegen Verfahrensnormen des MWSTG verstossen und damit das Bussenverfahren durch schuldhaftes Verhalten in analoger Anwendung von Art. 41 OR verursacht. Soweit er geltend mache, er habe am 5. März 2014 gegen die Betreibung der MWST-Forderung für das Jahr 2009 und am 28. März 2014 gegen jene für das 1. Quartal 2010 Einsprache erhoben und sich damit von der Steuerpflicht gemäss Art. 14 Abs. 5 MWSTG abgemeldet, könne ihm nicht gefolgt werden. Der Beschwerdeführer verkenne, dass mit dem Rechtsvorschlag in keiner Weise zum Ausdruck gebracht werde, was angefochten sei. Der Rechtsvorschlag müsse nicht begründet werden und könne sich auch bloss gegen die Höhe der in Betreibung gesetzten Forderung richten. Die ESTV habe bis zum Erlass des Strafbescheids vom 29. April 2014 keine Kenntnis davon gehabt, dass der Beschwerdeführer seine Steuerpflichtigkeit für das Jahr 2010 erneut bestreiten werde. In Bezug auf die Auskunfts- und Dokumentationspflicht des Beschwerdeführers reiche es zudem nicht aus, auf Belege zu verweisen, die in verschiedenen anderen Verfahren eingereicht worden seien. Der Beschwerdeführer habe rechtswidrig und schuldhaft die Einleitung des Strafverfahrens gegen ihn veranlasst, weshalb er die Kosten des Verwaltungsverfahrens und die Gebühr für das strafgerichtliche Verfahren zu tragen habe.
1.3. Die Auskunftspflicht nach Art. 68 Abs. 1 MWSTG setzt eine Anfrage der ESTV voraus (BEATRICE BLUM, in: Felix Geiger/Regine Schluckebier [Hrsg.], Kommentar MWSTG, 2012, N. 8 zu Art. 68 MWSTG). Inwiefern eine solche Anfrage erfolgte, legt die Vorinstanz nicht dar. Als solche könnte allenfalls die Mahnung vom 18. Februar 2014 oder das Schlussprotokoll vom 1. April 2014 verstanden werden, womit der Beschwerdeführer aufgefordert wurde, die Mehrwertsteuerabrechnung einzureichen. Im Grunde würde ihm damit allerdings wiederum das Nichteinreichen der Mehrwertsteuerabrechnung zum Vorwurf gemacht. Dies, obwohl die Vorinstanz die Unterlassung als nicht strafbar beurteilte. Darüber hinaus kann auch eine Pflichtverletzung nach Art. 68 Abs. 1 MWSTG strafrechtlich geahndet werden (BEATRICE BLUM, a.a.O., N. 12 zu Art. 68 MWSTG). Indem sich die Vorinstanz für die Kostenauflage auf eine Verletzung der Auskunftspflicht nach Art. 68 Abs. 1 MWSTG stützt, wirft sie dem Beschwerdeführer indirekt trotz Freispruchs ein strafrechtlich relevantes Verhalten vor. Dies ist bundesrechtswidrig.
Weiter begründet die Vorinstanz die Auferlegung der Kosten mit einer Verletzung von Art. 14 Abs. 5 MWSTG. Gemäss dieser Bestimmung muss sich die steuerpflichtige Person, die die gesetzliche Umsatzgrenze unterschreitet, abmelden. Eine entsprechende Abmeldung nahm der Beschwerdeführer nicht vor. Auf die Mahnung vom 18. Februar 2014 sowie das Schlussprotokoll vom 1. April 2014 reagierte er nicht. Es ist daher zutreffend, dass die ESTV, wie von der Vorinstanz ausgeführt, bei Erlass des Strafbescheids am 29. April 2014 keine Kenntnis davon hatte, dass der Beschwerdeführer die Mehrwertsteuerpflicht bestreitet. Insofern nahm dieser die Einleitung des Strafverfahrens in Kauf. Allerdings erwog die ESTV in ihrer Verfügung vom 10. November 2014, mit Eingaben vom 9. Mai 2014 und vom 22. September 2014 habe der Beschwerdeführer die Mehrwertsteuerpflicht als solche bestritten. Gegenstand des Einspracheverfahrens bilde somit die subjektive Steuerpflicht des Beschwerdeführers für die Steuerperiode 2010 (1. Januar 2010 bis 31. Dezember 2010). Unter diesen Umständen kann sich die Behörde spätestens ab dem 9. Mai 2014 nicht mehr darauf berufen, keine Kenntnis von der Bestreitung der Mehrwertsteuerpflicht gehabt zu haben. Indem die Vorinstanz dem Beschwerdeführer die Kosten des erstinstanzlichen Gerichtsverfahrens sowie die vollständigen Kosten des Verfahrens der Verwaltung auferlegt, verstösst sie gegen Art. 426 Abs. 2 StPO.
2.
Die Beschwerde ist gutzuheissen und die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen. Für das bundesgerichtliche Verfahren sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Dem nicht anwaltlich vertretenen Beschwerdeführer ist keine Parteientschädigung zuzusprechen (Art. 68 BGG; <ref-ruling> E. 4). Mit dem Entscheid in der Sache ist das Gesuch um aufschiebende Wirkung gegenstandslos geworden.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 27. November 2015 wird bezüglich der Kostenregelung aufgehoben und die Sache zu neuer 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, Ausschuss, sowie der ESTV schriftlich mitgeteilt.
Lausanne, 5. August 2016
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Schär