Angielska grupa założona w Ingatestone (Essex) w lutym 1979 z inicjatywy braci Bull - Richarda i perkusistę Rogera. Nazwa odnosiła się do królewskiej twierdzy we Francji, która służyła za więzienie i stanowiła dla ludu symbol ucisku. Bastylia została zburzona w lipcu 1789 w czasie zamieszek rozpoczynających rewolucję francuską, a potem kompletnie zburzona. Pierwszy skład zespołu uzupełnili: basista Colin Woodgate oraz dwójka gitarzystów: Mick Filby i Lee Carroll. W ciągu kilku następnych miesięcy nastąpiły roszady, na wskutek których Bastille stali się kwartetem. Na początku kariery chłopaki koncertowali wraz z Trespass w takich słynnych klubach jak londyński Marquee czy Mayfair w Newcastle. Potem dzielili scenę m.in. z Angel Witch, Samson, More i Alverna Gun. Wydawało się, że lada chwila zwrócą na siebie uwagę agentów muzycznych, którzy jeździli po Anglii, polując na młode talenty NWOBHM. "Demo 1979" zawierało trzy hard'n'heavymetalowe utwory (Rock Is My Life, Murder In The Rain, Breakout) - nagrania planowano oryginalnie wydać jako EP-kę w 1980, ale taśma-matka zaginęła (podobno odnaleziono ją dopiero w 2013). Z kolei na "Demo 1980" trafiły: Hard Man, You'd Better Run i nowa skrócona wersja Rock Is My Life. Pod koniec 1980 grupa zawiesiła działalność.
Richard Bull przewinął się przez skład Tank w kwietniu/maju 1981. Paul J. Ward grał potem z Misako Honjoh i w Di'Anno. Najlepszy zdecydowanie kawałek Bastille Hard Man trafił na składanki "New Electric Warriors" w 1980 i "Lightnin' To The Nations: NWOBHM 25th Anniversary Collection" w 2005.
UWAGA Pod koniec lat 80-tych działał w okolicach Mansfield inny heavymetalowy Bastille, który nagrał demówkę "Merciful Release" w 1988.