A Banda Municipal Paulense foi fundada a 4 de Setembro de 1874, sob a designação de Banda Filarmónica Paulense. A partir de 1991 passou-se a chamar Banda Municipal Paulense.

Entre os seus fundadores conhecem-se Manuel Gonçalves Jardim, mestre Arsénio (o 1.º mestre da Banda) e o Sr. Santana, o 1.º presidente.

Os mestres posteriores ao mestre Arsénio foram: Arseninho (filho do mestre), mestre António Coito, Manuel Bernardo Coito Andrade, António Coito, Manuel Balelo (Teixeira) e João Pedro Gomes Fernandes, actual regente, desde 1993.

Das saídas da banda estão registadas as seguintes:

12 de Julho de 1946 - Ida ao Porto Santo, que se iria repetir na década de 50 mais duas vezes;

1950 e 1953 a banda actuou no Funchal cinco vezes, duas em Câmara de Lobos, três na Serra D'Água e dez na Ponta do Sol.

As principais saídas eram no entanto os arredores do Paúl do Mar, onde a banda estava quase sempre presente. Assim refere-se Porto Moniz, Achadas da Cruz, Seixal, Santa, Prazeres, Fajã da Ovelha, Raposeira, Ponta do Pargo, Ribeira da Janela, Estreito da Calheta, Calheta e Jardim do Mar.

A banda angariava os seus fundos através dos Amadores, uma espécie de sócios, (actualmente contam com 52 sócios), que pagavam uma quota de dois escudos e meio por ano (1950). Em caso de necessidade os Amadores contribuíam com mais dinheiro. A banda tinha por tradição passar pelas casas dos Amadores na 1.ª oitava do Santo Amaro. No centenário da Banda foi criado um hino da autoria do mestre António Coito.

Salienta-se como curiosidade a participação da banda na comemoração do 1.º de Dezembro (Restauração) e 1.º de Janeiro (Ano Novo). Nestes dias, a banda, ainda hoje, percorre a freguesia do Paul do Mar logo pela manhã.

A Casa de Ensaio, situada no Serrado da Cruz, era o seu mais importante património até 1980. Com a degradação do edifício e a vandalização do mesmo, a banda perdeu a maior parte dos seus registos e arquivos. Actualmente os Ensaios são feitos no Sítio da Lagoa.

De referir que a Banda conta, actualmente, com 25/30 elementos.