A escola é oriunda de um evento tradicional no bairro da Cremação, conhecida como Malhação de Judas. A denominação Xodó da Nega foi sugerida por um dos membros da associação de malhadores de judas do bairro.
Em 2004 o bloco se tornou uma escola de samba e entrou para o terceiro grupo, conquistando o título de campeã logo na primeira disputa. No ano seguinte, subiu para o segundo grupo e também ganhou a disputa. Chegou ao grupo especial em 2006 e ficou em 7° lugar sendo rebaixada.
Em 2007, o Carnaval de Belém teve um Grupo Único com 14 escolas, onde as 7 primeiras continuariam no grupo especial e as 7 últimas cairiam para o Grupo de acesso; o Xodó ficou em 11°lugar e caiu. Em 2011, desfilou com o enredo "A Praça é nossa", que homenageava a Praça da República,[2] sendo campeã do Grupo 2 e obtendo novamente a ascensão.[3]
Em 2012 desfilou com o enredo "Todo mundo nasce nu, mas de roupa é mais bonito" na 7° colocação do grupo especial, e foi rebaixado novamente para o Grupo de Acesso. Em 2013 o Xodó não fez um bom carnaval e ficou na 6°Colocação do Grupo de Acesso. No ano de 2014, quando completou 25 anos de fundação, a agremiação foi campeã, retornando em 2015 ao grupo principal do Carnaval de Belém.
