Histórico

            A ocupação do morro do Corujá ou Tuiuti é tão antiga quanto a do bairro de São Cristóvão. Remonta aos tempos do Reinado e do Império. A primeira escola de samba do morro foi a Unidos do Tuiuti, que tinha as cores azul e rosa (e, depois, azul e branco), fundada em 1934.
            A escola, que teve um bom desempenho na década de 30 (conseguiu um honroso 3° lugar, abaixo apenas da Portela e da Mangueira), entrou em decadência na década de 40, surgindo então outras agremiações na comunidade, sendo a principal a Paraíso das baianas, de cores amarelo e branco.
            Depois da II Guerra Mundial, a Unidos do Tuiuti desapareceu, e em seu lugar nasceu o bloco por nome Bloco dos Brotinhos. O pessoal do morro, sem dinheiro para acompanhar carnaval mais sofisticado, preferia sair no bloco, desprezando a Paraíso das baianas. Foi então que um grupo de sambistas se reuniu, entre eles Nelson Forró e Júlio Matos (nesse tempo morava no morro), e resolveu terminar com o bloco e também com a Paraíso da baianas (A Unidos do Tuiuti não existia mais). E fundaram, em 5 de abril de 1954, a Paraíso do Tuiuti, que ganhou as cores amarelo e azul. O amarelo foi herdado da Paraíso das baianas e o azul, da Unidos.
            A atuação da nova agremiação, de inicio, foi discreta, mas em 1968, com o enredo de Júlio Matos homenageando o bairro de São Cristóvão, tira o 1° lugar no Grupo 3 e vai para o Grupo 2. Logo no ano Seguinte repete a atuação no Grupo 2, mas consegue apenas um terceiro lugar, com um ponto atrás da vicecampeã, a Unidos do Jacarezinho.
Em 1980, Maria Augusta Rodrigues, levada por Nelson Forró, faz seu primeiro trabalho para a Escola - "É a Sorte", e tira o titulo no Grupo 2-B. Júlio Matos colaborou muito com a escola, onde fez diversos carnavais.