1986-1992年，全省客运车辆基本是普通客车。虽然从国外引进桑诺斯(南斯拉夫产)和依卡露斯(匈牙利产)等高档客车，但因道路原因和旅客对客票票价承受能力的限制，高速客运未能发展。1993年12月，济南至青岛高速公路建成通车，省交通厅印发《济青高速公路旅客运输试营运一期工程实施方案》，提出加快发展济南至青岛的高速客运。同时，省交通厅专门组织筹集专项贴息贷款资金，统一购置33辆南京产依维柯中型客车，投入济青高速公路沿线参加试运行的6个大中型专业运输企业，启动济南至青岛高速公路快速客运市场。济南至青岛的高速客运开通以后，两地间的客运班车行驶时间，由原来的8小时左右缩短为4小时左右。
1996年2月，省交通厅公路运输管理局对济南汽车运输总公司《关于开通济南至青岛高速公路轿车客运的请示》作出批复，同意其与青岛市公路客运公司自1996年2月20日起进行济青高速公路轿车客运试营运业务，有关营运手续审批暂按道路客运班车规定执行。11月，山东交通济宇高速运业有限公司成立并开始运营。该公司由济南汽车运输总公司与韩国大宇株式会社合资成立，是全省第一家高速客运公司，总投资5200万元人民币，其中济南汽车运输总公司参股2600万元，占注册资本的50%，批准经营规模为30辆高档高速客车。随着高速公路发展以及高速公路网的逐步形成，山东省高速客运业迅猛发展。
1997年11月，济南长途运输公司与韩国锦湖建设公司合资成立济南锦湖客运有限责任公司。购置11辆沃尔沃客车及5辆凯斯鲍尔客车并投入运营。此后，济德高速、五星高速、东乡高速、黄河高速等十几家高速客运公司相继开业。
高速公路的陆续开通，带动高速客运快速发展。1998年，为加强高速客运管理，交通部印发《高速公路旅客运输管理规定》。省交通厅对全省高速公路客运经营资质进行严格审查，加强管理。同时，鼓励各地大力发展高速客运事业，要求实现规模化、网络化和集约化，以资产为纽带实现集团化经营。在省交通厅倡导下，全省各市(地)运输企业主动联合起来，通过各企业资金和资源的整合，使高速客运得到全面发展，提高了道路客运行业的整体竞争能力。
1999年7月，山东全直通高速客运股份有限公司成立揭牌仪式及新闻发布会在济南召开。济宇高速、锦湖高速、全直通等一大批经营高速客运的企业成立，标志着全省高速客运业的发展进入新阶段。至2000年底，全省开通高等级公路高速客运线路160条，营运里程4万多千米，拥有高级客车440部，开行高速客运班次1370个。2005年，随着全省高速公路通车里程增加和高速公路网形成，济南到其他16市均开通高速客运。