尧都区古称平阳，传为帝尧所都。周敬王六年（公元前514年）为晋国平阳县；战国时为韩武子初都之地。秦置平阳县，故治在今市区西南10千米金殿镇，属河东郡。西汉末王莽改香平，东汉复旧。三国魏正始八年（公元247年）于县置平阳郡。十六国时为刘渊都。前赵置雍州，后废。北魏太平真君二年（441年）禽昌县治徙今区境，属平阳郡。六年废平阳县。太和十一年（487年）复置，徙治今市区。孝昌二年（526年）侨置永安、隰城2县，寻于永安县侨置西河郡，2县俱属之。后废隰城县，置唐州，五城郡、县及定阳郡、县均徙治今区境，隶唐州。建义元年（528年）改晋州，徙治今市区。
东魏时定阳郡、县治徙今介休区境。天平四年（537年）于今区境置敷城郡、县，隶晋州。兴和二年（540年）于今区境置北五城郡。北周废五城、北五城2郡及敷城郡、县，禽昌县治徙今襄汾县境。隋开皇元年（581年）改平阳县为平河县、永安县为西河县、平阳郡为平河郡，废西河郡。三年废平河郡，改平河县为临汾县。大业三年（607年）改晋州为临汾郡。寻废西河县。义宁二年（618年）改临汾郡为平阳郡。
唐武德元年（618年）复置西河县，改平阳郡为晋州。三年升晋州为总管府，次年升都督府，治今市区。贞观六年（632年）废府，复为晋州。十七年西河县废入临汾县。天宝元年（742年）改晋州为平阳郡。乾元元年（758年）复为晋州。五代梁开平四年（910年）废晋州，置定昌军。贞明三年（917年）改建宁军。五代唐同光元年（923年）改建雄军。五代晋复为晋州。
宋太平兴国六年（981年）为晋州平阳郡。政和六年（1116年）升平阳府。金天会六年（1128年）于县置河东南路。兴定四年（1220年）于今市区西置平水县，属绛州。元废府，改河东南路为平阳路。大德九年（1305年）改晋宁路。明洪武元年（1368年）复为平阳府。后废平水县，于临汾县置河东道。民国初年废府、道，县直属省。
1948年析置临汾市，市、县俱属晋南区，为行署驻地。1949年撤市入县，属临汾专区，为专署驻地。1954年与运城专区合并为晋南专区，为专署驻地。1967年属晋南地区。1970年属临汾地区，为行署驻地。1971年（一说1970年8月）析置临汾市。1983年7月撤县入市。2000年11月1日，撤销临汾地区和县级临汾市设立地级临汾市和尧都区，临汾市更名为临汾市尧都区，以原县级临汾市的行政区划为都区的行政区划。区政府仍驻鼓楼东大街原址。地级临汾市政府驻尧都区解放西路。
1996年，临汾市（县级）面积1304平方千米，人口约62万人。辖8个街道、9个镇、16个乡：南街街道、车站街道、辛寺街道、鼓楼西街街道、乡贤街街道、水塔街道、解放路街道、铁路东街道、魏村镇、土门镇、吴村镇、大阳镇、乔李镇、北城镇、金殿镇、县底镇、刘村镇、西头乡、龙祠乡、尧庙乡、城隍乡、一平垣乡、郭行乡、东张乡、小榆乡、泊庄乡、贺家庄乡、大苏乡、段店乡、枕头乡、贾得乡、屯里乡、河底乡。市政府驻鼓楼东大街。
1999年3月8日，经省政府批准，将临汾市北城镇辖区划出，设立山西省临汾经济术开发区（省级）【该区位于临汾市区西北(原北城镇)，西起汾河东堤坝，东至平阳北街南起向阳西路，北到涝河泄洪渠。总规划面积7.8平方千米，起步区面积0.8平方千米】。
2000年2月28日，屯里乡改为屯里镇，原行政区划不变。同月，城市街道办事处所的贾庄、东关、西关、鼓楼南，挂甲庄、水门街、乡贤街、鼓楼北8个村委会改为14个居委会。6月26日，尧庙乡改为尧庙镇，原辖行政区划不变。
2000年第五次人口普查，尧都区常住总人口724403人，其中，解放路街道36673人，西街街道30648人，水塔街道16580人，南街街道40670人，乡贤街街道35161人，辛寺街街道17468人，路东街道52726人，车站街街道36245人，屯里镇16640人，乔李镇19156人，太阳镇18339人，县底镇25666人，刘村镇25891人，金殿镇26373人，吴村镇24022人，土门镇21737人，魏村镇13036人，北城镇16514人，尧庙乡18707人，殷店乡33156人，贾得乡33578人，东张乡15178人，郭行乡8552人，大苏乡9907人，城隍乡10428人，贺家庄乡7814人，泊庄乡19270人，小榆乡16308人，龙祠乡19836人，一平垣乡15527人，西头乡7008人，枕头乡18563人，河底乡10190人，果树厂6836人。
2001年3月，尧都区启动撤并乡镇调整区划工作，至4月底按计划完成。原14乡11镇调整为6乡10镇：泊庄乡并入刘村镇，大苏乡并入贾得乡，东张乡并入段店乡，西头乡并入土门镇，龙祠乡、小榆乡并入金殿镇，郭行乡并入大阳镇，城隍乡并入县底镇；屯里镇、尧庙镇、吴村镇、魏村镇、乔李镇、一平垣乡、枕头乡、河底乡、贺家庄乡保持原建制。同时，北城镇并入车站街街道；原果树场辖区改设汾河街道，水塔街、南街，铁路东、解放路、乡贤街、辛寺街、鼓楼西街7个街道行政区划不变。调整后，尧都区辖水塔街、南街、铁路东、解放路、乡贤街、辛寺街、鼓楼西街、车站街、汾河9个街道，屯里、尧庙、吴村、魏村、乔李、刘村、土门、金殿、大阳、县底10个镇和一平垣、枕头、河底、贺家庄、贾得、段店6个乡。（44个居委会、381个行政村）
2010年第六次人口普查，尧都区常住总人口944050人，其中，解放路街道60070人，鼓楼西街街道55999人，水塔街街道33649人，南街街道55876人，乡贤街街道58307人，辛寺街街道35856人，铁路东街道94098人，车站街街道40590人，汾河街道9690人，屯里镇20530人，乔李镇18105人，大阳镇22428人，县底镇33518人，刘村镇56850人，金殿镇65795人，吴村镇23178人，土门镇29948人，魏村镇14364人，尧庙镇37017人，段店乡43174人，贾得乡47737人，贺家庄乡4352人，一平垣乡15981人，枕头乡19114人，河底乡10111人，滨河办事处37713人。
？年，设立滨河街道。
2015年末，尧都区辖10个街道、10个镇、6个乡（合计26个），57个居委会、372个村委会（合计429个）。