唐元和四年（809）以符离、蕲县及虹县置宿州，治埇桥，即今宿州市区。1912年废州为宿县。1979年宿县析城关镇及近郊置宿州市，1992年市县合并为宿州市。
1998年12月6日，国务院批准：撤销宿县地区和县级宿州市，设立地级宿州市。市人民政府驻新设立的埇桥区。宿州市设立埇桥区，以原宿州市的行政区域为埇桥区的行政区域。
1996年，宿州市（县级）面积2865平方千米，人口约154.2万人，辖8个街道、16个镇、13个乡：西关街道、南关街道、东关街道、道东街道、沱河街道、埇桥街道、北关街道、三里湾街道、芦岭镇、符离集镇、褚兰镇、曹村镇、栏杆镇、夹沟镇、时村镇、永宁镇、汴河镇、灰古镇、大店镇、桃园镇、蕲县镇、大营镇、朱仙庄镇、西寺坡镇、杨庄乡、解集乡、支河乡、桃沟乡、蒿沟乡、顺河乡、苗庵乡、永镇乡、三八乡、城东乡、龙王庙乡、西二铺乡、北杨寨乡。
2000年第五次人口普查，埇桥区常住总人口1601181人，其中，埇桥街道23456人，沱河街道30969人，道东街道23885人，东关街道32879人，三里湾街道31689人，南关街道49460人，西关街道35135人，北关街道30876人，符离镇85511人，芦岭镇74069人，朱仙庄镇75701人，褚兰镇44420人，曹村镇58145人，夹沟镇59409人，栏杆镇67303人，时村镇74821人，永安镇52313人，汴河镇30815人，灰古镇29814人，大店镇67358人，西寺坡镇34264人，桃园镇31548人，蕲县镇60722人，大营镇36235人，杨庄乡36720人，支河乡32400人，解集乡51099人，桃沟乡31901人，顺河乡38702人，蒿沟乡44588人，苗庵乡42563人，龙王庙乡21661人，北杨寨乡61961人，永镇乡25533人，三八乡37492人，西二铺乡17958人，城东乡17806人。
2004年，埇桥区乡镇由29个调整为24个，将龙王庙乡整建制并入西寺坡镇；将桃园镇、北杨寨乡整建制合并，设立新的桃园镇，镇政府迁往北杨寨集；撤销城东乡、三八乡、汴河镇，分别设立城东街道、三八街道、汴河街道，为埇桥区政府的派出机构；其余乡镇保留不变。调整后，埇桥区辖11个街道、15个镇、9个乡。
2009年，经省政府同意，省民政厅批复，将桃园镇的河拐、后付2个居委会，王桥、闫店、李桥、刘合、邵王5个村委会和三里湾街道的王徐居委会、陈营居委会以及城东街道的七里村委会划出，设立金海街道（金海街道办事处于4月30日正式挂牌成立，辖4个居委会，6个村委会，面积18.17平方公里，人口31751人，办事处驻宿州经济开发区）。
2010年第六次人口普查，埇桥区常住总人口1647642人，其中，埇桥街道46306人，沱河街道36182人，道东街道29764人，东关街道45219人，三里湾街道32274人，南关街道70203人，西关街道64278人，北关街道35015人，汴河街道29428人，三八街道49505人，城东街道17830人，金海街道37647人，符离镇77011人，芦岭镇76845人，朱仙庄镇82499人，褚兰镇42692人，曹村镇53754人，夹沟镇47824人，栏杆镇52866人，时村镇62687人，永安镇44403人，灰古镇27994人，大店镇69044人，西寺坡镇50511人，桃园镇81469人，蕲县镇62256人，大营镇34550人，杨庄乡31498人，支河乡28346人，解集乡48511人，桃沟乡25266人，顺河乡35555人，蒿沟乡37733人，苗安乡41794人，永镇乡21036人，西二铺乡16960人，夹沟农场887人。
2012年1月18日，宿州马鞍山现代产业园区经省政府批准成立，由马鞍山、宿州市合作共建，享受省级开发区政策。托管埇桥区部分乡镇（东部新城行政管会、蒿沟乡、苗庵乡），面积253平方千米。
2014年2月11日，省民政厅（民地字[2014]28号）批复同意西寺坡镇更名为大泽乡镇。