Il passe son enfance à Toulon. Sa famille, soupçonnée de pétainisme alors que le père était en constante relation avec son beau-frère, un des plus anciens compagnons de la résistance, préfère quitter cette ville après la guerre. Il entre à l'École polytechnique, dont il est diplômé en 1955.
Il produit les premiers
Jean Eustache, était l'ami de
Jacques Demy et dirige son idole
Danielle Darrieux. Il collabore aux Cahiers du Cinéma et à La Revue du cinéma, avouant une passion notamment pour
Robert Bresson, Jean Grémillon et Max Ophuls.
Françoise Lebrun a souvent joué pour Paul Vecchiali, dont le diptyque sur les rapports post-amoureux Trous de mémoire (1984) et sa "suite" À vot' bon coeur (2004).
Son cinéma s'inspire du cinéma français des années 1930, avec une touche expérimentale (Paul Vecchiali préfère "recherche") et de l'autobiographie.
Il réalise son premier film en 1961, un film muet, tout en travaillant comme officier-instructeur à Polytechnique.
C'est le cinéaste des sentiments, de l'espace, de la mobilité. De l'invention, de la surprise et de la contradiction. Avec lui le mot "dialectique" prend tout son sens - esthétique et moral. Il aborde le thème du sida. De l'homosexualité, de la bisexualité, de la non sexualité; de la peine de mort, de la religion, de la passion : tout fait thème chez Paul Vecchiali, l'un des plus inventifs cinéastes français depuis les années trente. Il faut aussi et surtout remarquer l'extraordinaire puissance de travail de ce cinéaste, également producteur, écrivain, découvreur, inventeur. Il a tourné, avec les productions pour la télévision, plus d'une cinquantaine de films. Il n'a obtenu que quatre fois l'avance sur recettes du CNC, ce qui lui a inspiré le scénario de "À vot' bon coeur", une "farce" musicale où les membres du comité sont assassinés les uns après les autres. Il a souvent eu du mal à monter ses films : mais il raconte avec fierté qu'à l'exception d'un seul, tous ont rapporté davantage qu'ils n'ont coûté.
Comme le note le dictionnaire du cinéma français des années 70 de Cinéma 80 : "Qu'il aborde le fantastique (L'étrangleur), la comédie musicale (Femmes, femmes), la pornographie (Change pas de main), la pédophilie et la peine de mort (La machine), l'épuration sanglante qui suivit la Libération (En haut des marches), la prostitution (Rosa la Rose), ou le romanesque (Corps à coeur, C'est la vie), Vecchiali impose une vision du monde originale, éminemment subversive dans la mesure où tout, inné et acquis, concourt à décortiquer le réel de ce qui l'opacifie, idées ou regards reçus".
François Truffaut fera partie des rares personnes à s'enthousiasmer pour Vecchiali à ses débuts. A la projection des "Les Ruses du diable", François Truffaut déclare : "Paul Vecchiali est le seul héritier de Jean Renoir".
Jacques Demy quant à lui déclare à Paul Vecchiali : "On n'est peut-être que tous les deux à aimer
Robert Bresson et
Danielle Darrieux"...
Il vit depuis 2006 dans le Var à Plan de la Tour.