En agosto de 2004 Paula Meijide formó el grupo que lleva su nombre, y que actualmente integran: Pablo Raposo en piano, Gerardo de Mónaco en contrabajo, Javier Martínez en batería, Santiago de Francisco en saxo, Santiago Castellani en trombón y James Suggs en trompeta.

Ya desde 1999 había integrado diferentes grupos como el de Carlos Cirigliano (con Alfredo Remus y Hugo Pierre) y el de Fernando Lupano (con Patán Vidal y Adrián Fusta) y había trabajado con músicos como Javier Lozano y Mariano Otero.

Como solista, y luego de presentarse en numerosos lugares del circuito de jazz porteño, en enero de 2005 participó en el Festival de Jazz de Necochea, cerrando el evento junto a Wálter Malosetti.

En julio de ese mismo año grabó su primer disco, en el que incluyó composiciones propias, el mismo fue presentado en Notorious el 22 y 30 de noviembre de 2005, en dos shows junto a todo el grupo, con excelentes críticas de la prensa porteña. Estaba acompañada por Pablo Raposo en piano, Gerardo de Mónaco en contrabajo, Eloy Michelini en batería, Santiago Castellani, Santiago de Francisco y Nahuel Aschei en vientos.

Entre junio del 2005 y junio del 2006 formó parte del grupo Entre Rios.

En mayo de 2006 se presentó, junto a sus músicos, en el Festival de Jazz de Buenos Aires.