Après le lycée, il s'engage à 18 ans dans les Marines. Deux années plus tard, démobilisé, il s'inscrit à l'université de Louisville, ou il suit des études de littérature et d'anthropologie. Il y intègre la troupe de théâtre. En 1954 il tente de percer à Broadway mais n'obtient que de petits rôles dans des émissions de télévision, et part tenter sa chance à Hollywood. Il apparaît dans de nombreuses de séries entre 1957 et 1965, notamment : 77 Sunset Strip, the Rifleman, Wagon train, Rawhide, Gunsmoke ou encore The Twilight zone.
Warren Oates fait ses débuts au cinéma sous la direction du réalisateur Gordon Douglas, dans La Mission secrète du sous-marin X.16 (1959) puis dans Le Géant du Grand Nord (1959). Dès lors, l'acteur s'illustre dans des westerns, le plus souvent dans des rôles de truands : frère tuberculeux dans La Chute d'un caïd (Budd Boetticher, 1959), prospecteur crasseux dans Coups de feu dans la sierra (Sam Peckinpah, 1961), ou encore dangereux tueur dans les films de Burt Kennedy (Le Retour des sept, 1966) et de Monte Hellman (The Shooting, 1966). Ce dernier lui offre plus tard le premier rôle de Macadam à deux voies (1970) avant que Warren Oates n'interprète le rôle-titre de Dillinger (John Millius, 1973) qui décrit l'ascension et la chute d'un pilleur de banques. Du rôle de braqueur, il passe à celui de cambrioleur maladroit dans Têtes vides cherchent coffres pleins (William Friedkin, 1978). Au début des années 1980, Warren Oates tourne dans 1941 (Steven Spielberg, 1979) et dans Tonnerre de feu (John Badham, 1983).
Parallèlement au cinéma, Warren Oates poursuit sa carrière à la télévision, reprenant notamment les rôles de Rooster Cogburn, tenu au cinéma par John Wayne, dans True Grit (Richard T. Heffron, 1978) et celui de Charlie Allnutt (Humphrey Bogart) dans African Queen (1977).