2000年12月26日，由铁道部和各铁路局共同出资，以铁路通信系统为基础的铁道通信信息有限责任公司成立。2001年2月28日，铁道通信信息有限责任公司山东分公司成立，主要经营本地网电话、国内长途电话、IP电话、数据传送、互联网、视讯、卡类、呼叫中心、虚拟专网、网络托管、传真存储转发等基础电信业务和增值业务。
2001年， 山东铁通设立综合部、人事劳动部、财务部、规划建设部、市场部、互联互通办公室、党群部、网络部、寻呼部、铁道事业部和综合信息部11个职能部门。2001年4月底，完成济南、青岛、泰安、徐州4个省管分公司的组建工作；9月底，陆续完成济宁、临沂、淄博、潍坊、聊城、烟台、威海、东营、日照、菏泽、莱芜、枣庄和连云港13个分公司的组建工作，初步建成以原铁路通信大格局为基础、覆盖全省的组织网络。2002年，为理顺管理关系，将潍坊、淄博、聊城、济宁、临沂、日照、烟台7个市管分公司升格为省管分公司，并分别调整了济南分公司与泰安分公司、淄博分公司，济宁分公司与临沂分公司，济宁分公司与聊城分公司的管界，使生产经营格局更加清晰。至2002年底，形成了9个省管分公司、7个市管分公司的初步管理格局（滨州由淄博代管，德州属河北铁通）。省管分公司下设综合部、财务部、计划建设部、铁道业务部、党群部等部门和二级中心，按县（市、区）下设经营分局，负责本辖区业务经营；市管分公司设综合部、建设部、铁道业务部3个部门，网络覆盖县（市、区）设立经营分局。
2003年2月1日，组建山东铁通工程建设有限责任公司（简称工程公司）。9月，根据公专网分类管理的要求，成立济南、青岛、徐州和兖州4个铁道服务中心，后改为铁道通信中心，并与江苏、天津、河南、安徽4个省公司联合完成徐州、德州分公司及有关地区的属地化管理工作。经营公网的徐州分公司划归江苏铁通，原河北铁通德州分公司划入山东铁通。
2004年1月20日，国资委、铁道部联合下发《关于将铁道通信信息有限责任公司移交国资委管理有关问题的通知》，铁道通信信息有限责任公司由铁道部移交国资委管理，更名为中国铁通集团有限公司，成为国家基础电信运营商之一。2004年8月，铁道通信信息有限责任公司山东分公司更名为中国铁通集团有限公司山东分公司，根据行政区划设立17个市级分公司，根据铁路管区设立相应的铁道通信中心。同年，将威海、莱芜、东营、枣庄4个市管分公司升格为省管分公司，新组建滨州分公司，均纳入山东铁通直管。
2005年，山东铁道通信中心实行三级管理，撤销通信段、部分电话所、电报所，组建营销服务部门。年底，山东铁通形成由17个市分公司、4个铁道通信中心、1个实业公司和山东铁通本级构成的经营管理架构。山东铁通管理部门由原来的15个精简为9个，管理人员由原来的98人精简为60人。山东铁通本级设市场部、网运部、铁业部、建设部、人力资源部、财务部、审计部、综合部和党群部9个职能部门，辖直属重点客户部、综合信息服务中心、营收管理中心、网络支撑中心和铁道通信客服部5个生产经营单位。
2001—2005年中国铁通集团有限公司山东分公司负责人一览表
表1—6
┏━━━━━━━━━┯━━━━━━━━━━━━━━┯━━━━━━━━━━━━━━━┓
┃ 姓 名 │ 职 务 │ 任职时间 ┃
┠─────────┼──────────────┼───────────────┨
┃ 闫世文 │ 总经理 │2001.02—2005.03 ┃
┃ ├──────────────┤ ┃
┃ │ 党委书记 │ ┃
┠─────────┼──────────────┼───────────────┨
┃ 段宝文 │ 总经理 │2005.04— ┃
┃ ├──────────────┤ ┃
┃ │ 党委书记 │ ┃
┠─────────┼──────────────┼───────────────┨
┃ 徐书群 │ 党委副书记 │2001.02—2003.12 ┃
┠─────────┼──────────────┼───────────────┨
┃ 胡克振 │ 副总经理 │2001.03—2005.03 ┃
┠─────────┼──────────────┼───────────────┨
┃ 王 砺 │ 副总经理 │2001.03—2005.09 ┃
┠─────────┼──────────────┼───────────────┨
┃ 李国光 │ 副总经理 │2001.03—2004.12 ┃
┠─────────┼──────────────┼───────────────┨
┃ 李 华 │ 总会计师 │2002.01— ┃
┠─────────┼──────────────┼───────────────┨
┃ 陈兴进 │ 副总经理 │2004.08— ┃
┠─────────┼──────────────┼───────────────┨
┃ 董志良 │ 副总经理 │2005.09— ┃
┠─────────┼──────────────┼───────────────┨
┃ 赵 荣 │ 副总经理 │2005.09— ┃
┗━━━━━━━━━┷━━━━━━━━━━━━━━┷━━━━━━━━━━━━━━━┛