C’est à la Slade School of Fine Art de Londres où elle étudie la peinture (1952-1956), que Paula Rego rencontre son futur mari, l’artiste et critique Victor Willing. David Sylvester la remarque pour son œuvre Under Milk Wood (1954). Restée au Portugal jusqu’en 1963, elle partage ensuite sa vie entre son pays natal et la Grande-Bretagne, avant d’émigrer définitivement et de résider à Londres à partir de 1976. Dans les années 1960, la découverte décisive de l’œuvre de Dubuffet exerce une influence libératrice sur son travail. À la suite des expositions simultanées dans les galeries londoniennes de Saatchi et Marlborough (1994), la critique la range parmi la seconde génération de l’école de Londres, aux côtés de Francis Bacon et de Lucian Freud.
Sa peinture exprime une critique violente à l’égard de son pays, et notamment du régime salazariste, qui dominera l’histoire nationale portugaise quarante ans durant (Salazar Vomiting the Homeland, 1960). D’autres thèmes émergent dans sa peinture, comme celui des relations conjugales et des relations homme-femme (en 1998, elle réalise Triptyque, sur le thème de l’avortement). Présence physique et brutale des êtres, violence des relations humaines dans lesquelles les enfants jouent un rôle majeur et ambigu (fétichisme, sadomasochisme), sens de la mise en scène, importance de la figure de l’animal sont des thèmes prédominants de son œuvre. Quant à ses sources, elle explique : « C’est ça pour moi la littérature, des histoire violentes, magiques, dans lesquelles il y a des punitions, des châtiments. Des choses liées à l’éducation des enfants. »

Elle combine et superpose des souvenirs d’histoires populaires, des récits d’histoire du Portugal et des contes de son enfance. Benjamin Rabier, Gustave Doré ou Francisco de Goya imprègnent durablement l’iconographie et la construction narrative de son œuvre (A menina com cão [Petite fille avec un chien], 1986). Sur un plan technique, elle se singularise par un réel talent de coloriste et de dessinatrice. À la peinture à l’huile, elle préfère le crayon, le pastel, l’acrylique ou le collage (Manifesto for a Lost Cause, 1966 ; Stray Dogs [Dogs of Barcelona], 1965). Poursuivant les thèmes de l’enfance et du statut de la femme, elle se lance dans la réalisation de figures à taille humaine en papier mâché qui animent une sorte de carnaval intime. En septembre 2009, un nouveau musée, la Maison des histoires Paula-Rego, construit par l’architecte portugais Eduardo Souto de Moura et dédié à son œuvre, a ouvert à Caiscais, près de Lisbonne.