D'une famille de cinq enfants, Paul Mercieca est orphelin de père en 1939. Titulaire du certificat d'études, il se forme au métier de menuisier[1].
Il adhère à la CGT en 1949 et au Parti communiste en 1950. Il prend des responsabilités au sein des Jeunesses communistes.
Il épouse le 25 juillet 1959 à Vitry-sur-Seine Monique Maréchal (née en 1935), secrétaire générale de l’UJFF (1962-1968) et conseillère générale PCF du canton de Vitry-sur-Seine-Ouest (1967-1988). Paul Mercieca est élu conseiller municipal de cette commune le , puis succède à Marcel Rosette en tant que maire lors de son élection au Sénat.
En 1980, les médias s'emparent de l'affaire dite du « bulldozer de Vitry » : une troupe dirigée par le maire communiste dévaste un foyer pour immigrés dans lequel devaient être logés des travailleurs maliens. Selon son biographe Claude Pennetier, cette affaire « doit être placée dans le contexte de la montée du chômage en France, des réactions de l’opinion mettant en rapport immigration et chômage et dans celui de la proximité des élections présidentielles ».
En 1982, il devient député du Val-de-Marne en remplacement de Georges Gosnat décédé. Il est réélu en 1986 et 1993, mais abandonne ce mandat et celui de maire en 1996.