Ryska planer på att upprätta ett fort i södra Uralbergen kallat Orenburg uppkom 1734. Kolonister grundlade det ursprungliga Orenburg 1735 där Uralfloden sammanfaller med Or (stadens namn betyder "fortet vid Or"). Denna bosättning bytte dock namn till Orsk år 1739. Ett försök gjordes att grunda ett annat Orenburg vid Krasnogar, "röda kullen", år 1741, men detta misslyckades. Ett tredje Orenburg uppfördes med framgång av Ivan Nepljujev år 1743 på stadens nuvarande plats, cirka 250 km nedför Ural från Orsk.
Orenburg fungerade som en viktig militär utpost på gränsen mot de nomadiska kazakerna och staden blev centrum för Orenburgkosackerna. Efter att Centralasien införlivats med det ryska riket blev Orenburg på 1800-talet en betydande handelsstad och en viktig järnvägsknut på vägen mot de nya centralasiatiska besittningarna och mot Sibirien.
Orenburg spelade en viktig roll i Jemeljan Pugatjovs uppror 1773-1774. Staden var då huvudort i ett stort distrikt och säte för guvernören i guvernementet Orenburg. Pugatjov belägrade staden från det närliggande Berda från oktober 1773 till 26 mars1774. Försvaret organiserades av generallöjtnant Reinsdorp. Generalen Golitsyn besegrade Pugatjev vid Berda, och senare vid Kargala (norr om Orenburg). Större delen av staden hade då fallit i ruiner och tusentals invånare hade dött i belägringen.
Staden var vidare en viktig omlastningsstation på Sidenvägen som sammanband området med Centralasien och Kina - här fanns dessutom en betydande produktion av gjutjärnskärl, framförallt för export till Afghanistan fram till omkring 1925.
Mellan 1938 och 1957 bar staden namnet Tjkalov (ryska: Чка́лов) efter testpiloten Valerij Tjkalov. Avståndet mellan staden och de invaderande tyska styrkorna i andra världskriget gjorde att många sovjetiska företag lokaliserades till staden, vilket främjade dess ekonomiska tillväxt. Orenburg är också känt som den plats där kosmonauten Jurij Gagarin lärde sig flyga. Han gick på en teknisk skola i staden när en flygklubb vid ett metallföretag i staden fångade hans intresse. Efter ihärdiga studier i avionik, aerodynamik liksom praktisk flygning infriades hans drömmar om ett liv i det blå. Han antogs som elev i det sovjetiska flygvapnet och började flyga MiG-15. Gagarin blev bara några år senare den första ryska kosmonauten och den första människan att färdas i omloppsbana runt jorden.
