W ten sposób powstał nowy tytuł, tygodnik, który zrodził się w redakcji i tu przybrał ostateczny kształt.
31 stycznia 1956 ukazał się ostatni numer „Na Straży Wybrzeża”, a 3 lutego 1956 pierwszy numer „Bandery”, w formacie gazetowym, o objętości 12 stron. Zmieniono sposób łamania, wzrosła liczba publikowanych zdjęć. Zaczęły dominować reportaże, wywiady i felietony. Pojawiły się działy tematyczne, kąciki poświęcone rozrywce. Drukowano opowiadania oraz fragmenty książek marynistycznych.
W następnych latach „Bandera” wielokrotnie zmieniała szatę graficzną i format, trwając nieustannie jako tygodnik o zmiennej objętości.
„Bandera” towarzyszyła Marynarce Wojennej w jej codziennym życiu, dążąc do nawiązania trwałych kontaktów z czytelnikami, przede wszystkim z marynarzami służby zasadniczej. Na początku lat 60. zmniejszył się format pisma, wzrosła natomiast objętość – do 24 stron. Wydawano wówczas przez dłuższy okres dodatki „Żeglarz”, „Nasze sprawy”, „Porywy” – wraz z podchorążymi WSMW oraz numery specjalne i tzw. małe wydania „Bandery”, kompendia wiedzy niezbędnej dla marynarzy rozpoczynających służbę w Marynarce Wojennej.