济宁市烟草专卖局、山东济宁烟草有限公司成立之初为济宁市烟草专卖局、山东省烟草公司济宁分公司，二者合署办公，1984年6月，划归山东省烟草专卖局（公司）管理。1994年9月，鲁南烟草集团公司成立，山东省烟草公司济宁分公司归属鲁南烟草集团公司管理。1995年6月，试行政企分开，山东省烟草公司济宁分公司撤销。1998年1月，鲁南烟草集团公司与颐中烟草（集团）有限公司合并组建颐中烟草（济宁）有限公司，与济宁市烟草专卖局合署办公。1998年8月，山东烟草购销（集团）有限公司成立，颐中烟草（济宁）有限公司隶属山东烟草购销（集团）有限公司，更名为山东烟草购销（集团）有限公司济宁分公司。2000年6月，山东烟草购销（集团）有限公司撤销，9月，山东烟草购销（集团）有限公司济宁分公司改制为山东济宁烟草有限公司。2005年10月，济宁市烟草专卖局（有限公司）下辖市中区、任城区、兖州市、曲阜市、泗水县、邹城市、微山县、鱼台县、金乡县、嘉祥县、汶上县、梁山县12个县（市、区）烟草专卖局（营销部）。2010年，总资产13.60亿元，固定资产1.30亿元，流动资产11.77亿元；全系统共有从业人员1371人，其中聘用员工939人。
1991—2010年，济宁市烟草专卖局（有限公司）历经多次改革，烟草专卖在创新中不断强化，行业管理水平大幅度提升，基础设施建设规模逐渐壮大，独具特色的企业文化建设得到巩固完善，领导班子、干部队伍、职工素质明显提高。卷烟销售量由1991年的17万箱增加到2010年的28万箱，提高了65个百分点；销售收入由2.74亿元增加到36.79亿元，增长14倍，利税由670万元增加到4.37亿元，增长64倍。
全市专卖管理工作不断加大人力、物力投入，逐步健全内部管理制度，强化稽查执法力度，全面清理整顿卷烟市场，监管流通渠道，开展打假打私等。20年间，市县两级烟草专卖局共查处违法案件11.78万起，查获各类违法卷烟17.94亿支，案值1.44亿元，捣毁大型制假窝点208处，拘留566人，判刑201人。两级烟草专卖局建立完善的专卖管理网络，烟草专卖许可证实行A、B、C户分类管理，开展星级经销户和卷烟经营模范商店评选活动。1995年，济宁市烟草专卖局被国家烟草专卖局评为“全国烟草系统打假工作先进集体”，2000—2004年连续5年被山东省烟草专卖局评为“全省烟草专卖管理先进单位”。市县两级烟草专卖局13次被国家局、省政府评为打假打私、综合治理、公正执法等先进单位。全市有12人次被省以上主管部门、政府机关记功，授予劳动模范、“金叶卫士”“打假能手”等荣誉称号。