1995年5月，省邮电管理局从瑞典爱立信公司引进数字移动通信电话系统，至1996年，共进行4期工程建设。1998年1月19日，数字移动通信GSM系统一期至四期工程交付使用。
1998年4月，全省数字移动通信网OSS、SOG扩容工程（即GSM五期工程）竣工投产，扩建网管系统OSS一套，扩建SOG系统一套。
1999年5月31日，山东省GSM数字移动通信第六期工程完成并全网投入运行。该工程新增移动交换机（MSC）30台、基站控制器（BSC）15台，新增基站（BTS）782个，扩容基站391个，新增载频8331个，新增交换用户容量258万户。该工程完成后全网拥有42台MSC、36台BSC，无线容量可容纳用户270万户。
1999年7月山东移动通信公司成立后，为满足无线通信的需要，在前6期GSM网工程的基础上，又陆续进行6期工程建设。
GSM网七期工程。1999年9月底开始，2000年4月底竣工，新建基站591个，扩建基站349个，新增载频3223个，新增交换用户容量169万户。至此，全省GSM数字移动通信网拥有42台移动交换机、36台基站控制器、8套HLR/AUC系统，全省县以上城市和98%以上的乡镇实现无缝覆盖。
GSM网八期工程。2001年9月竣工，新建宏蜂窝基站1266个，扩建基站1277个，增加载频13193个（不含微蜂窝），新增交换用户容量334.44万户。该工程完成后，全省GSM数字移动通信网拥有71台移动交换机（含TMSC2和GMSC）、61台基站控制器、17套HLR/AUC系统，实现省内全覆盖，彻底解决了全省村村通电话的难题，并为GPRS网络搭建了良好的支撑平台。
GSM网九期工程。2002年11月竣工，新增交换机8台、基站控制器13台、4套HLR/AUC。新增基站2392个，新增载频10581个，新增交换用户容量261.56万户。该工程完成后，全省GSM数字移动通信网拥有75台移动交换机（含TMSC2和GMSC）、74台基站控制器、21套HLR/AUC系统。
GSM网十期工程。2003年12月建设完成，新建基站649个，新增载频3743个，新增交换用户容量189万户。该工程完成后，全省GSM数字移动通信网拥有80台移动交换机、81台基站控制器、23套HLR/AUC系统。
GSM网十一期工程。2004年11月完成。全省新建基站1471个，新增载频12524个，新增交换用户容量476万户。
GSM网十二期工程。2005年10月完成，新建基站662个，新增载频2.7万个，新增GSM网元76个（总数达到267个），新增交换用户容量523万户。该工程完成后，全省共拥有TMSC1设备2套，TMG/SG设备1套、TMSC2设备4套、HSTP设备2套、LSTP设备4套、端局交换机（MGC）86套、基站控制器108套、独立HLR/AUG系统32套、独立端口局交换机（GMSC）11套，载频总量87000个，可满足2323万用户需求。
2004年，中国移动启动长途软交换网一期工程、IP专用承载网一期工程建设，在济南设置了SS及TMG/SG设备，通过IP网进行省际长途17951话务的转接。
至2005年，山东移动电话交换网采用三级网络结构，在济南设有一对TMSC1设备，负责省际话务转接，在济南、青岛各设1对TMSC2设备，分别负责东西部业务区的省内话务转接。
1996—2005年山东移动GSM工程建设完成主要指标情况一览表
表4-3
┏━━━━┯━━━━━━━━━━━┯━━━━━━━━━━┯━━━━━━━━━━━━┓
┃ 年 份 │ 基站总量（个） │ 载频总量（个、块） │ 交换用户总容量（万户） ┃
┠────┼───────────┼──────────┼────────────┨
┃ 1996 │ 370 │ │ 27.5 ┃
┠────┼───────────┼──────────┼────────────┨
┃ 1997 │ 812 │ │ 55.4 ┃
┠────┼───────────┼──────────┼────────────┨
┃ 1998 │ 1436 │ │ 112.6 ┃
┠────┼───────────┼──────────┼────────────┨
┃ 1999 │ 2218 │ 13871 │ 370 ┃
┠────┼───────────┼──────────┼────────────┨
┃ 2000 │ 2809 │ 17904 │ 539 ┃
┠────┼───────────┼──────────┼────────────┨
┃ 2001 │ 3488 │ 33552 │ 873.44 ┃
┠────┼───────────┼──────────┼────────────┨
┃ 2002 │ 5880 │ 43733 │ 1135 ┃
┠────┼───────────┼──────────┼────────────┨
┃ 2003 │ 6529 │ 47476 │ 1324 ┃
┠────┼───────────┼──────────┼────────────┨
┃ 2004 │ 8000 │ 60000 │ 1800 ┃
┠────┼───────────┼──────────┼────────────┨
┃ 2005 │ 8662 │ 87000 │ 2323 ┃
┗━━━━┷━━━━━━━━━━━┷━━━━━━━━━━┷━━━━━━━━━━━━┛
说明：1996—1998年无载频数据