A criação da Brigada Ambiental do Recife foi anunciada em 1999 durante solenidade realizada pela prefeitura, às margens do Açude de Apipucos, em 5 de junho - Dia Mundial do Meio Ambiente. Uma portaria conjunta, das Secretarias de Serviços Públicos (SSP) e de Planejamento e Meio Ambiente (Seplam), datada de 30 de julho de 1999, estabeleceu oficialmente a brigada.
Inicialmente, formada por um grupo de 10 integrantes da Guarda Municipal do Recife, vinculada à época à SSP, operava em escala diurna, se segunda a sexta-feira. Em seguida, o efetivo foi ampliado para 18 pessoas, que trabalhavam em escala de 12 por 36 horas, incluindo os finais de semana, mas apenas durante o dia.
Desde o ato de criação vinculada à Seplam, a Brigada Ambiental iniciou seus trabalhos numa sala de imóvel da prefeitura localizado na Rua Afonso Pena, nº 550, no bairro de Santo Amaro. Em 2010, foi transferida para a antiga sede do 12º Batalhão da Polícia Militar de Pernambuco, no Parque Jiquiá, no bairro da Mangueira.
Em dezembro de 2013, a atual Secretaria de Meio Ambiente e Sustentabilidade (Smas), construiu a sede própria da Brigada, nas dependências do Jardim Botânico do Recife.