Frédéric Vitoux est le fils de Pierre Vitoux, journaliste au Petit Parisien condamné à la Libération pour intelligence avec l’ennemi. Il est aussi le petit-fils de Georges Vitoux, journaliste scientifique et docteur en médecine.
Frédéric Vitoux a suivi ses études secondaires à l’école Massillon, puis au lycée Charlemagne à Paris. Élève de mathématiques supérieures dans cet établissement après son bac, il prépare cependant le concours d’entrée à l’IDHEC (Institut des hautes études cinématographiques) puis bifurque vers des études littéraires : licence de lettres à la Sorbonne puis doctorat de troisième cycle, en 1968, avec une thèse consacrée à Louis-Ferdinand Céline. À partir de 1966, il écrit aussi dans la revue de cinéma Positif.