Sachverhalt:
A.
Die Staatsanwaltschaft des Kantons Basel-Stadt wirft X._ zusammengefasst vor, er habe sich spätestens am 26. November 2014 mit seinem Bruder zusammengeschlossen, um gemeinsam und in arbeitsteiliger Weise eine unbestimmte Vielzahl geparkter Personenwagen in unrechtmässiger Bereicherungsabsicht aufzubrechen, nach Wertgegenständen und Bargeld zu durchsuchen sowie allfällige Funde mitzunehmen. Dazu hätten sie zwei präparierte Schraubendreher mit T-Griff mit sich geführt. X._ habe sein Fahrzeug zur Verfügung gestellt und als Fahrer sowie Aufpasser fungiert, während sein Bruder mehrheitlich die Personenwagen aufgebrochen, durchsucht, das Deliktsgut mitgenommen sowie im gemeinsam genutzten Wagen gelagert habe. Am Abend des 26. November 2014 hätten sie in der Zeit von 17.00 Uhr bis 20.30 Uhr an drei verschiedenen Orten (Parkhaus an der Hochbergerstrasse 70, Hermann Klinkelin-Strasse und St. Alban-Rheinweg) drei Personenwagen aufgebrochen, durchsucht und aus zweien verschiedene Gegenstände entwendet. Einen weiteren Personenwagen hätten sie versucht aufzubrechen, wobei sie den akustischen Alarm ausgelöst hätten.
B.
In Bestätigung des Urteils des Strafgerichts des Kantons Basel-Stadt vom 18. Februar 2015 sprach das Appellationsgericht des Kantons Basel-Stadt X._ am 21. Juni 2016 wegen bandenmässigen Diebstahls und mehrfacher Sachbeschädigung schuldig. Es verurteilte ihn zu einer Freiheitsstrafe von acht Monaten und zur Zahlung von Fr. 277.15 an einen Privatkläger, dies unter solidarischer Haftung mit seinem Bruder.
C.
X._ beantragt mit Beschwerde in Strafsachen, das appellationsgerichtliche Urteil sei teilweise aufzuheben und er sei vom Vorwurf des bandenmässigen Diebstahls sowie der Sachbeschädigung in Ziff. I.a) und I.b) der Anklageschrift freizusprechen. Er sei einzig des Diebstahls sowie der Sachbeschädigung in Ziff. I.c) der Anklageschrift schuldig zu sprechen und zu einer schuldangemessenen, bedingt vollziehbaren Geldstrafe, bei einer Probezeit von drei Jahren, zu verurteilen. Eventualiter sei das Urteil aufzuheben und die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen.
D.
Während die Staatsanwaltschaft beantragt, auf die Beschwerde sei nicht einzutreten, schliesst das Appellationsgericht auf Abweisung der Beschwerde.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt den Anklagegrundsatz als verletzt. Die für die Qualifikation der Bandenmässigkeit wesentlichen Sachverhaltselemente seien in der Anklageschrift vom 7. Januar 2015 nicht umschrieben. Es fehle an Ausführungen zur Hierarchie und dem Innenleben der angeblichen Bande. Die von der Vorinstanz geschilderte Sachverhaltsdarstellung gehe nicht über jene einer "normalen" Mittäterschaft hinaus. Vielmehr hätte aufgezeigt werden müssen, worin sich das Zusammenwirken innerhalb der angeblichen Bande manifestiert hätte und inwiefern das vorgeworfene Handeln über das einer einfachen Mittäterschaft hinausgegangen wäre.
1.2. Die Vorinstanz erwägt, in der Anklageschrift würden nicht nur der rechtliche Vorwurf der Bandenmässigkeit, sondern auch die wesentlichen, für die Beurteilung dieses Qualifikationsmerkmals notwendigen Tatsachen ausdrücklich genannt: das gemeinsame Vorgehen, die unbestimmte Vielzahl der Delikte, das mitgenommene präparierte Werkzeug und die Konkretisierung des Tatbeitrags des Beschwerdeführers. Die Angabe von Zeit und Ort veranschauliche in eindrücklicher Weise, dass die Täter innerhalb eines Zeitraums von nur dreieinhalb Stunden in verschiedenen Stadtteilen aktiv geworden seien und auf dem Parkplatz am St. Alban-Rheinweg gleich zwei Autos aufgebrochen hätten. Auch ergebe sich, dass sie von ihrer Einbruchserie abgelassen hätten und geflüchtet seien, weil ein Alarm ausgelöst worden sei. Der Anklagegrundsatz sei offensichtlich nicht verletzt (Urteil S. 6 f.). Auch sei die Qualifikation wegen Bandenmässigkeit zu bestätigen. Die aufgezählten Hinweise auf die gemeinsam beschlossene und durchgeführte Verübung mehrerer selbstständiger Straftaten seien erwiesen. Im Vergleich zum Grundtatbestand hätten die beiden Täter vorliegend in relativ kurzer Zeit vier Einbrüche verübt und seien dafür gezielt über eine weite Strecke angereist. Sie seien organisiert sowie arbeitsteilig vorgegangen und hätten sich dadurch gegenseitig zur Tat bestärkt. Das Vorgehen zu zweit habe einem der beiden ermöglicht, Schmiere zu stehen und zu fahren. Der andere habe sich ganz auf den Einbruch konzentrieren können. In allen diesen Umständen liege die gesteigerte Vorwerfbarkeit der Bandenmässigkeit begründet. Aufgrund der Aussagen der beiden Brüder sei von einer gelebten geschwisterlichen Verbundenheit auszugehen, was von der bundesgerichtlichen Rechtsprechung als Beispiel für die gegenseitige psychische Stärkung zweier Täter genannt werde (Urteil S. 7).
1.3. Nach dem Anklagegrundsatz bestimmt die Anklageschrift den Gegenstand des Gerichtsverfahrens (Umgrenzungsfunktion; Art. 9 und Art. 325 StPO; Art. 29 Abs. 2 sowie Art. 32 Abs. 2 BV; Art. 6 Ziff. 1 und Ziff. 3 lit. a sowie lit. b EMRK). Das Gericht ist an den in der Anklage wiedergegebenen Sachverhalt gebunden (Immutabilitätsprinzip), nicht aber an dessen rechtliche Würdigung durch die Anklagebehörde (vgl. <ref-law>). Die Anklage hat die der beschuldigten Person zur Last gelegten Delikte in ihrem Sachverhalt so präzise zu umschreiben, dass die Vorwürfe in objektiver und subjektiver Hinsicht genügend konkretisiert sind. Das Akkusationsprinzip bezweckt zugleich den Schutz der Verteidigungsrechte der beschuldigten Person und dient dem Anspruch auf rechtliches Gehör (Informationsfunktion; <ref-ruling> E. 3.4.1 S. 142 f.; <ref-ruling> E. 1.3 S. 190; <ref-ruling> E. 6.2 f. S. 244 f.; je mit Hinweisen). Die beschuldigte Person muss unter dem Gesichtspunkt der Informationsfunktion aus der Anklage ersehen können, wessen sie angeklagt ist. Das bedingt eine zureichende Umschreibung der Tat. Entscheidend ist, dass der Betroffene genau weiss, welcher konkreter Handlungen er beschuldigt und wie sein Verhalten rechtlich qualifiziert wird, damit er sich in seiner Verteidigung richtig vorbereiten kann. Er darf nicht Gefahr laufen, erst an der Gerichtsverhandlung mit neuen Anschuldigungen konfrontiert zu werden (vgl. <ref-ruling> E. 1b S. 6 f.; Urteile 6B_1151/2015 vom 21. Dezember 2016 E. 2.2, zur Publikation vorgesehen; 6B_492/2015 vom 2. Dezember 2015 E. 2.2, nicht publ. in: <ref-ruling>; je mit Hinweisen).
Gemäss Art. 139 Ziff. 3 Abs. 1 und 2 StGB macht sich des bandenmässigen Diebstahls schuldig, wer den Diebstahl, d.h. die Wegnahme einer fremden beweglichen Sache zur Aneignung, als Mitglied einer Bande ausführt, die sich zur fortgesetzten Verübung von Raub oder Diebstahl zusammengefunden hat. Nach der Rechtsprechung ist Bandenmässigkeit gegeben, wenn zwei oder mehrere Täter sich mit dem ausdrücklich oder konkludent geäusserten Willen zusammenfinden, inskünftig zur Verübung mehrerer selbstständiger, im Einzelnen möglicherweise noch unbestimmter Straftaten zusammenzuwirken. Zweck der Qualifikation ist die besondere Gefährlichkeit, die sich daraus ergibt, dass der Zusammenschluss die Täter stark macht und die fortgesetzte Verübung solcher Delikte voraussehen lässt (<ref-ruling> E. 2 S. 158 und E. 3.3 S. 161; <ref-ruling> E. 5.2 S. 137; <ref-ruling> E. 2b S. 88 f.; 78 IV 227 E. 2 S. 233; 72 IV 110 E. 2 S. 113). Es ist nicht erforderlich, dass sich jeder Einzelne an den Straftaten der Bande beteiligt (TRECHSEL/CRAMERI, in: Schweizerisches Strafgesetzbuch, Praxiskommentar, 2. Aufl. 2013, N. 17 zu <ref-law>; STRATENWERTH/WOHLERS, Schweizerisches Strafgesetzbuch, Handkommentar, 3. Aufl. 2013, N. 11 zu <ref-law>; Niggli/Riedo, in: Basler Kommentar, Strafrecht, Bd. II, 3. Aufl. 2013, N. 121 und 131 zu <ref-law>). Selbst derjenige Täter handelt bandenmässig, der einen Diebstahl oder Raub allein ausführt, sofern er dies in der Erfüllung der ihm in der Bande zustehenden Aufgabe begangen hat (<ref-ruling> E. 5 S. 147; 78 IV 227 E. 2 S. 234; Urteile 6B_42/2016 vom 26. Mai 2016 E. 2.2; 6B_980/2014 vom 2. April 2015 E. 1.3; je mit Hinweisen). Eine Bande kann nach der Rechtsprechung schon beim Zusammenschluss von zwei Tätern gegeben sein, wenn nur gewisse, über die blosse Mittäterschaft hinausgehende Mindestansätze einer Organisation (etwa einer Rollen- oder Arbeitsteilung) vorliegen oder die Intensität des Zusammenwirkens ein derartiges Ausmass erreicht, dass von einem bis zu einem gewissen Grade fest verbundenen und stabilen Team gesprochen werden kann, auch wenn dieses allenfalls nur kurzlebig war (<ref-ruling> E. 2 und 3 S. 158 ff.; <ref-ruling> E. 2b S. 88 f.; Urteil 6B_510/2013 vom 3. März 2014 E. 3.3 mit Hinweisen). Der Begriff der Bande ist eng auszulegen (Urteile 6B_510/2013 vom 3. März 2014 E. 3.3; 6P.104/2004 vom 24. März 2005 E. 3; NIGGLI/RIEDO, a.a.O., N. 122 zu <ref-law>).
1.4. Der Anklagegrundsatz ist nicht verletzt. Der Vorinstanz ist zuzustimmen, dass die für die Beurteilung des Qualifikationsmerkmals der Bandenmässigkeit relevanten Tatsachen in der Anklageschrift umschrieben werden. So wird einleitend in allgemeiner Hinsicht ausgeführt, zu welchem Zweck sich die beiden Brüder zusammenschlossen, was sie jeweils mitführten und wie sie die verschiedenen Rollen aufteilten. In den lit. a bis c werden in der Folge die einzelnen Vorfälle unter Angabe von Zeit, Ort, Tatbeitrag des Beschwerdeführers sowie seines Bruders, Einbruchsobjekt, geschädigte Person, Höhe des Schadens und - im Falle von lit. a und b - Wert des Diebesguts näher dargelegt. Damit umschreibt die Anklageschrift den Anklagevorwurf hinreichend bestimmt, so dass für den Beschwerdeführer klar erkennbar war, welches konkrete Vorgehen ihm vorgeworfen und wie sein Verhalten rechtlich qualifiziert wird. Im kantonalen Verfahren war er denn auch ohne weiteres in der Lage, seine Verteidigungsrechte angemessen auszuüben. Ob sich jedoch die einzelnen Sachverhaltselemente auch tatsächlich erstellen lassen und gegebenenfalls unter den eng auszulegenden Begriff der Bande zu subsumieren sind, ist eine Frage der Beweiswürdigung sowie der rechtlichen Würdigung.
Die Vorinstanz wird ihre Sachverhaltsfeststellung und Beweiswürdigung neu begründen müssen (vgl. E. 2). Obwohl folglich noch kein verbindlicher Sachverhalt vorliegt (vgl. <ref-law>), erscheint es aus prozessökonomischen Gründen gerechtfertigt, bereits an dieser Stelle auf die Einwände des Beschwerdeführers gegen die Qualifikation der Bandenmässigkeit einzugehen. Selbst wenn vom angeklagten und vorinstanzlich festgestellten Sachverhalt ausgegangen würde, läge keine Bandenmässigkeit vor. Wie der Beschwerdeführer zutreffend vorbringt, zeigt die Vorinstanz nicht auf, welche konkreten Anhaltspunkte darauf schliessen liessen, dass er und sein Bruder in Zukunft gemeinsam weitere Diebstähle hätten verüben wollen. Diesbezüglich hält die Vorinstanz einzig fest, die aufgezählten Hinweise auf die gemeinsam beschlossene und durchgeführte Verübung mehrerer selbstständiger Straftaten sei erwiesen (Urteil S. 7). Auch in der Anklageschrift wird lediglich allgemein festgehalten, dass der Beschwerdeführer und sein Bruder sich zusammengeschlossen hätten, um gemeinsam sowie in arbeitsteiliger Weise eine unbestimmte Vielzahl geparkter Personenwagen aufzubrechen. Das Bundesgericht hat jüngst in einem Urteil darauf hingewiesen, dass für die Annahme bandenmässiger Tatbegehung anhand konkreter Tatumstände aufgezeigt werden muss, dass sich die Täter mit dem Willen zusammenschlossen, mehrere selbstständige, im Einzelnen noch unbestimmte Straftaten zu verüben. Auf diesen Willen, der zumindest konkludent manifestiert worden sein muss, kann nicht allein retrospektiv gestützt auf die Tatsache geschlossen werden, dass zwei oder mehrere Täter eine Reihe von Delikten in enger örtlicher und zeitlicher Nähe auf ähnliche Weise verübt haben (Urteil 6B_510/2013 vom 3. März 2014 E. 3.4.2 mit Hinweis auf Urteil 6P.104/2004 vom 24. März 2005 E. 4). Aus der Anklageschrift und den vorinstanzlichen Ausführungen ergeben sich keine Hinweise, dass der Beschwerdeführer beabsichtigt hätte, über eine gewisse Zeit hin zusammen mit seinem Bruder in einer über eine kurze Dauer hinausgehende Verbindung unbestimmt viele Diebstähle zu begehen. Dass die beiden in relativ kurzer Zeit vier Personenwagen aufgebrochen haben und gezielt über eine weite Strecke angereist sein sollen, ändert daran nichts. Im Weiteren ergibt sich weder aus der Anklageschrift noch den vorinstanzlichen Ausführungen, dass die beiden mutmasslichen Täter besonders intensiv zusammenwirkten, einen höheren Organisationsgrad gehabt oder die Diebstähle speziell geplant hätten. Zwar geht die Vorinstanz von einer organisierten Arbeitsteilung aus, die es einem der Brüder ermöglicht habe, sich auf den Einbruch zu konzentrieren. Jedoch kann dies nur beschränkt zutreffen, da der Beschwerdeführer gemäss Anklageschrift beim ersten Diebstahl getankt haben soll. Insgesamt geht das angebliche Zusammenwirken des Beschwerdeführers und seines Bruders nicht über jenes bei Mittäterschaft hinaus. Die Anforderungen an eine bandenmässige Tatbegehung sind vorliegend nicht erfüllt.
2.
2.1. Der Beschwerdeführer rügt, die Vorinstanz verletze ihre Begründungspflicht und damit seinen Anspruch auf rechtliches Gehör (<ref-law>; <ref-law>). Sie gehe weder auf die einzelnen Anklagepunkte ein noch setze sie sich mit seinen konkreten Vorbringen oder der Beweislage auseinander. Ebenso wenig stelle sie einen massgebenden Sachverhalt dar oder zeige seinen jeweiligen Tatbeitrag auf. Vielmehr habe sie sich auf die pauschale Feststellung beschränkt, sein Bruder und er hätten die Reise nach Basel mit dem Ziel angetreten, Autodiebstähle zu verüben, weshalb kein Zweifel bestehe, dass sie gemeinsam delinquiert hätten.
2.2. Aus dem Anspruch auf rechtliches Gehör folgt die Pflicht der Behörden, ihren Entscheid zu begründen. Die Begründung muss kurz die wesentlichen Überlegungen nennen, von denen sich das Gericht hat leiten lassen und auf die es seinen Entscheid stützt. Die Behörde darf sich aber auf die massgebenden Gesichtspunkte beschränken und muss sich nicht ausdrücklich mit jeder tatsächlichen Behauptung und jedem rechtlichen Einwand auseinandersetzen und diese widerlegen. Es genügt, wenn sich der Betroffene über die Tragweite des Entscheids Rechenschaft geben und ihn in voller Kenntnis der Sache an die höhere Instanz weiterziehen kann (<ref-ruling> E. 3.2.4 S. 41; <ref-ruling> E. 2.2 S. 183; <ref-ruling> E. 2.2 S. 84; je mit Hinweisen; Urteil 6B_979/2016 vom 20. Februar 2017 E. 2.2.2).
2.3. Die Vorinstanz gibt zunächst kurz zusammengefasst die Erkenntnisse des erstinstanzlichen Gerichts wieder. Es folgen die Einwände des Beschwerdeführers, theoretische Ausführungen zu Beweiserhebungen im Rechtsmittelverfahren, die Nennung der objektiven und subjektiven Beweismittel sowie theoretische Ausführungen zum Grundsatz "in dubio pro reo" (Urteil S. 2 ff.). Daraufhin erwägt die Vorinstanz, der Beschwerdeführer und sein Bruder seien am Abend des 26. November 2014 im Personenwagen des Beschwerdeführers angehalten worden. Darin hätten sich zwei Schraubendreher und das Deliktsgut aus zwei weiteren Autoeinbrüchen befunden. Die DNA-Spur am Schraubendreher weise auf den Beschwerdeführer hin, der den Personenwagen bei der Anhaltung gelenkt habe. Seine Angabe, sie hätten ein Fussballspiel besuchen wollen, stimme mit der zurückgelegten Route nicht überein. Seine Aussagen wirkten wenig glaubhaft. Auch widerspreche es der Lebenserfahrung, dass der Beschwerdeführer nicht gemerkt haben will, wie sein Bruder während der Fahrt durch Basel unbekannte Gegenstände in das Auto geladen habe. Aufgrund der gemeinsamen Fahrt, der im Auto gefundenen Tatwerkzeuge und der im Fahrzeug transportierten Beute sei davon auszugehen, dass beide Brüder die Reise nach Basel bereits mit dem Ziel angetreten hätten, an diesem Abend gemeinsam Autodiebstähle zu begehen. Es bestünden keine massgeblichen Zweifel daran, dass die beiden Brüder nicht nur zusammen unterwegs gewesen seien, sondern bei dieser Gelegenheit auch gemeinsam delinquiert hätten (Urteil S. 5). Diesen Ausführungen folgt die rechtliche Würdigung und die Beurteilung der Frage, ob der Anklagegrundsatz hinsichtlich des Qualifikationsmerkmals der Bandenmässigkeit verletzt sei (vgl. E. 1; Urteil S. 5 ff.). Schliesslich misst die Vorinstanz die Strafe zu und setzt die Kosten fest (Urteil S. 7 ff.).
2.4. Die Beschwerde ist in diesem Punkt begründet. Weder ergibt sich aus dem vorinstanzlichen Urteil, was dem Beschwerdeführer konkret vorgeworfen wird, noch stellt die Vorinstanz abschliessend fest, welchen Sachverhalt sie als erstellt erachtet und ihrer rechtlichen Würdigung zu Grunde legt. Ebenso wenig findet eine eigentliche Beweiswürdigung statt. Auch verweist die Vorinstanz diesbezüglich nicht auf die erstinstanzlichen Ausführungen (vgl. <ref-law>; erstinstanzliches Urteil S. 6 ff.). Die Vorinstanz verfügt über umfassende Kognition in tatsächlicher und rechtlicher Hinsicht (vgl. Art. 398 Abs. 2 und 3 StPO). Tritt sie auf die Berufung ein, fällt sie ein neues, den erstinstanzlichen Entscheid ersetzendes Urteil (vgl. <ref-law>; <ref-ruling> E. 1.3.3 S. 248; Urteil 6B_70/2015 vom 20. April 2016 E. 1.4.2; je mit Hinweisen), wobei sie den Sachverhalt neu feststellen kann (vgl. Urteil 6B_1302/2015 vom 28. Dezember 2016 E. 4.2.1). Der Beschwerdeführer hat im kantonalen Verfahren stets bestritten, Personenwagen aufgebrochen oder Kenntnis von den entsprechenden Tätigkeiten seines Bruders gehabt zu haben (erstinstanzliches Urteil S. 6; Berufungsbegründung S. 3 ff.). Die Vorinstanz hätte sich folglich mit seinen Vorbringen auseinandersetzen, die Beweise selbst würdigen und den rechtserheblichen Sachverhalt feststellen müssen. Da sie hiervon absah, kann das Bundesgericht nicht prüfen, ob ihre Beweiswürdigung willkürlich ist. Das vorinstanzliche Urteil ist ungenügend begründet und verletzt das rechtliche Gehör des Beschwerdeführers sowie <ref-law>.
2.5. Eine Heilung dieser Verletzung des rechtlichen Gehörs kommt im bundesgerichtlichen Verfahren nicht in Betracht (vgl. <ref-ruling> E. 2.8.1 S. 226; <ref-ruling> E. 2.3.2 S. 197 f.; je mit Hinweisen). Dies führt zur Aufhebung des angefochtenen Urteils, ohne dass die weiteren Rügen zu prüfen wären (siehe BGE <ref-ruling> E. 2.2 S. 197; <ref-ruling> E. 2.6.1 S. 285; vgl. auch <ref-law>).
3.
Die Beschwerde ist teilweise gutzuheissen, das angefochtene Urteil aufzuheben und die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen. Im Übrigen wird die Beschwerde abgewiesen.
Der Kanton Basel-Stadt hat dem Beschwerdeführer für das bundesgerichtliche Verfahren im Umfang seines Obsiegens eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG). Soweit der Beschwerdeführer unterliegt, hat er für die Gerichtskosten aufzukommen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen, das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 21. Juni 2016 aufgehoben und die Sache zu neuer Entscheidung an das Appellationsgericht zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen.
2.
Dem Beschwerdeführer werden Gerichtskosten von Fr. 1'000.-- auferlegt.
3.
Der Kanton Basel-Stadt hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 7. April 2017
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Andres