Paljas zag het licht op 1 juli 1965. In die tijd werd tijdens een Jongerenweek van de St.Andreasparochie het Jongerencontact Mozaïek opgericht, met als doel het organiseren van feesten en culturele activiteiten. De oprichting bleek een schot in de roos, ook al omdat er toen voor de jongeren niet veel te doen was in het stadje Zevenaar. Er ontstonden binnen het Jongerencontact diverse afdelingen met een eigen bestuur. Naast een toneelclub en een ziekenomroep werd op 1 juli 1965 een carnavalsclubje met de naam Paljas opgericht. De geestelijkheid vond het allemaal prima als het RK-stempel maar behouden zou blijven. De jongeren van toen hadden daar blijkbaar geen moeite mee. Je kunt ook zeggen: “men wist niet beter”.

Het eerste clubhuis van Mozaïek stond aan de Wittenburgstraat. Later trok men in een vervallen boerderij “waar de waterpomptang als flessenopener dienstdeed”. Je zag toen ook veel jongeren in Hotel Café de Vier Tamboers en Hotel Restaurant De Leeuw aan het Raadhuisplein. Daarna kreeg Mozaïek een eigen onderkomen. Er bestaan nog steeds dankbare herinneringen aan het jongerencentrum Eureka, dat naast de huidige brandweerkazerne stond en, wel heel toevallig, op steenworp afstand van het huidige clubhuis van Paljas aan de Engeveldweg. In Eureka begon de groei van Paljas. In de eerste jaren werd maar één carnavalsavond gehouden in zaal Jansen-Rekers, nu bekend als De Griethse Poort aan de Oude Doesburgseweg. Na twee jaar verkaste men naar De Buitenmolen, dat tot op de dag van vandaag de residentie van het Paljas-carnaval is gebleven.