Depois da fraca (e muito injustiçada) recepção de “Severino”(1994), e com o lançamento de “Vamos Bater Lata” (1995), segundo álbum ao vivo da banda e que tinha como bônus um CD com 4 faixas inéditas, entre elas “Uma Brasileira”, grande sucesso tanto de vendas, como de público nos shows, os Paralamas começaram uma sequência de álbuns onde priorizaram a criação de canções pop sem deixar de se preocupar com a qualidade das mesmas e também a forte (e sadia) intenção de procurar novos elementos e formas de deixar sua música sempre atual.

Vindos de outro grande sucesso (“9 Luas” de 1996), que trazia as músicas: “Loirinha Bombril”, “Busca Vida” e "La Bella Luna", e com os planos de gravar um “Acústico MTV” logo em seguida, mas adiado para não coincidir com massivo sucesso obtido pelos Titãs o seu acústico, os Paralamas vindos da sempre constante e cheia agenda de shows, ficaram de outubro a dezembro de 1997, gravando o seu álbum sucessor nos estúdios do produtor Chico Neves.

Trabalhando com Chico Neves pela primeira vez e utilizando de forma mais intensa as novas tecnologias disponíveis na época como o sistema ProTools de gravação, Herbert, Bi e Barone trabalharam com vários tipos de microfones, procurando a melhor ambiência (posição dos amplificadores com relação aos microfones em diferentes lugares) para gravar os instrumentos e com isso criar sons marcantes e distintos para todas as músicas.

Uma das intenções de Herbert era que esse álbum tivesse uma presença forte de guitarras e fez questão de que as duas faixas iniciais ("Por Sempre Andar" e "Depois da Queda O Coice") deixassem isso bem claro. A primeira é bem blueseira, com um riff de guitarra que percorre a música toda, no mesmo ritmo em que Herbert canta a urgência de não se poder parar e deixar pequenas coisas para trás. "Depois da Queda O Coice" apesar de serem os metais que dão peso a música a guitarra preenche todos os espaços com arpejos e riffs.Vale ressaltar que o nome do CD foi tirado do refrão dessa música e segundo os próprios Paralamas por falta de uma opção melhor.

Como a intenção era fazer um álbum Pop com sofisticação e tendo a lição que “Severino” trouxe a eles bem assimilada, algumas novas experimentações foram realizadas e com a ajuda de Chico Neves fazendo uma participação bem ativa no processo criativo do álbum, uma presença bem parecida com o que George Martin fazia com os Beatles, criando sons e nuances para cada música como, por exemplo "O Trem da Juventude" com sua levada soft, belo arranjo de metais e um violão swingado e empolgante. "Brasília 5:31" é uma quase bossa-nova com uma letra que reflete o dia a dia de viagens da banda e suas amarguras e friezas, vale destacar a participação de Dado Villa-Lobos nessa faixa tocando guitarra com o efeito E-Bow.

Em "O Amor Não Sabe Esperar" Marisa Monte divide os vocais, fazendo a música ficar ainda mais marcante (uma curiosidade a respeito dessa música, é que a intenção inicial era que Tim Maia a cantasse junto de Marisa, o “síndico” já havia sido sondado e concordou em participar, mas na hora H ele não apareceu e Herbert acabou fazendo o vocal.

O grande sucesso do CD foi o Reggae Pop "Ela Disse Adeus" que rendeu aos Paralamas um videoclipe antológico com a participação da atriz Fernanda Torres e ganhou vários prêmios no VMB da MTV, até hoje é um dos pontos forte dos shows dos Paralamas. "Scream Poetry" traz letra de Chico Science e participação de Jorge Mautner, é uma bela homenagem dos Paralamas a Chico, com som bem próximo ao que Nação Zumbi fazia junto a Chico.

Uma das grandes músicas de “Hey Na Na” é "Viernes 3 AM" música de Charly Garcia (da época em que ele tocava no banda argentina Serú Girán) e letra vertida ao português por Herbert, traz os versos dilaceradores sobre: paixão, dor, ódio, desespero, onde Herbert canta de forma catártica cada palavra e destila nota por nota de uma guitarra sensacional, que aliada ao vocal de Cecília Spyer traz uma emoção semelhante a causada por “The Great Gig in the Sky” do Pink Floyd no álbum “The Dark Side Of The Moon” quando a escutamos.

O álbum fecha com duas baladas: "Um Dia Em Provença" e "Santorini Blues" ambas com belos vocais bem ao estilo dos Beach Boys. A primeira feita em parceria com Thedy Correa do Nenhum de Nós, e a segunda composta por Herbert quando estava passando férias nas ilhas Gregas e se encantou com a beleza da região e que também acabou dando nome ao seu segundo disco solo lançado em 1997.

Com “Hey Na Na” os Paralamas fecharam a década de 90 com um maravilhoso álbum que agora já passados 15 anos de seu lançamento permanece atual e bem perto do som que é criado hoje em dia, prova da qualidade das músicas, da produção e da visão sempre ampla e única dos Paralamas na confecção de seus discos, que nos fazem descobrir e redescobrir novos detalhes a cada audição.

“Hey Na Na” foi o ultimo álbum de inéditas lançado pelos Paralamas antes do acidente de Herbert Viana em 2001, nesse meio tempo eles lançariam ainda o ótimo “Acústico MTV” (1999) e a coletânea “Arquivo 2” (2000), o próximo álbum “Longo Caminho” (2002) seria gravado com músicas já feitas por Herbert antes do acidente e com uma nova direção e abordagem que já era planejada pelo trio anteriormente.