W latach 1954/1954 grupa występowała w warszawskim lokalu „Czerwona Oberża” przy ul. Żurawiej oraz w KS „Polonia” przy ul. Foksal. Opracowywanie programu muzycznego zespołu podzielili między siebie Matuszkiewicz i Trzaskowski. W tym czasie muzycy dawali występy w Krakowie i Łodzi. Ze względu na trudności z lokalami, odbywały się one przeważnie w prywatnych mieszkaniach (np. pięciopokojowe mieszkanie p. Fersterów w Krakowie) skupiając coraz większą ilość wielbicieli (wśród nich Andrzej Kurylewicz – wówczas student Krakowskiej Szkoły Muzycznej). W związku z tymi trudnościami na początku listopada 1954 w wynajętej sali gimnastycznej (w jednej z krakowskich szkół podstawowych) zorganizowano festiwal „Zaduszki Jazzowe”, który był jednym z pierwszych takich wydarzeń w Polsce.
Po zmianach przez władze polityki kulturalnej w kraju Państwowe Przedsiębiorstwo Imprez Estradowych zaczęło angażować zespoły jazzowe na występy. Dzięki tym imprezom (warszawski „Jam Session No. 1” – w marcu 1955, „Turniej Jazzowy” w Hali Gwardii, czy impreza „Studio '55”) Melomani zdobyli popularność w całej Polsce. 5 stycznia 1958, jako pierwszy zespół jazzowy, wystąpił w Filharmonii Narodowej w Warszawie, inaugurując cykl koncertów przedstawiających najlepsze polskie grupy i gości.