Veřejná Bezpečnost byla založena v zimě 2004 při jedné náhodné sešlosti na ulici. Opravdu se začíná hrát až od 1. dubna 2006, do této doby se skupina snažila sehnat nástroje a pořádné členy skupiny.

Původní sestava: Johny, Capitain Sensible, Dave. Na konci prázdnin přichází nový bubeník Jirka Podhorný a zpěvačka Klára Stachová. Na podzim bubeník a zpěvačka odchází a přichází nový zpěvák Tomáš Gottvald. Tomáš dostal přezdívku Gotty a je v bandě až do dneška.

Po půl roce přichází na místo bubeníka Petr Svačina. V této sestavě odehráli tři velmi důležité koncerty a nahráli Demo - "Nekomentuj to a vypadni". Po roce přichází klávesistka Eva Novotná a druhý kytarista Martin Vrchovský. Ale po čase zůstává kapela hrát zase jen ve čtyřech.

Kapela má za sebou u
účasti na akcích jako Brněnec fest, Podparou, Recykl fest. V roce 2008 vychází první regulérní album HA!HA!HA!, vydané na vlastní náklady.