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.