Seit den Anfängen der filmischen Arbeit von Ulrich Seidl spielt die Schauspielerin Maria Hofstätter darin eine wichtige Rolle. Kennengelernt haben sie einander bei einem TV-Porträt über den Karikaturisten Gerhard Haderer (1994). Ihren Durchbruch feierte sie dann als preisgekrönte Autostopperin in „Hundstage“ (2001). Gedreht hat Maria Hofstätter mit den Größen der Österreichischen Branche: von Michael Haneke („Wolfszeit“) bis Michael Glawogger („Ameisenstraße“). Jenseits des Films verbringt Maria Hofstätter die meiste Zeit mit ihrer Theaterarbeit. Seit 1983 tritt sie an verschiedenen Bühnen zwischen Wien, Feldkirch und Berlin auf, auch in eigenen Inszenierungen und Kabaretts. Seit 1995 leitet sie gemeinsam mit Dietmar Nigsch das Projekttheater Vorarlberg.
Der Ägypter Nabil Saleh ist schauspielerischer Laie und für „PARADIES: Glaube“ stand er zum ersten Mal vor der Kamera. Aufgewachsen in Alexandria, lebte er seit 1972 als Weltenbummler in Europa, zwischen Griechenland, Großbritannien, Frankreich, Norwegen und Deutschland. Seit 1980 lebt er in Österreich, wo er als Masseur arbeitet. Entdeckt wurde Nabil Saleh im Zuge eines monatelangen Castings in Wien. „Ich bin Ausländer in Wien und hatte die gleichen Probleme wie die Figur im Film, mit Inländern, Ausländern und Frauen“, sagt er. Für die Rolle in „PARADIES: Glaube“ hat er monatelang unter ergotherapeuthischer Anleitung das Rollstuhlfahren trainiert. Noch fordernder waren für den Laiendarsteller die Gewaltszenen: „Wenn man jemandem weh tun muss und das eigentlich gar nicht will.“ Zuletzt spielte er eine Hauptrolle in Seidls Theaterinszenierung „Böse Buben/Fiese Männer”, ein Stück basierend auf den Texten von David Foster Wallace.