1891年6月,清政府成立北洋官铁路局,开始修建山海关站舍和机车房,这是中国官办的第一条铁路。
1893年5月,津榆铁路修到山海关,关外铁路开始动工。
1903年7月,东清铁道南部支路(长大铁路)建成通车,是由沙皇俄国投资修建并控制。当时为宽轨1.524米。同时在哈尔滨成立东清铁道管理局。
1905年12月3日,由日本军队修建的安奉铁路(安东至奉天)修建完工(窄轨0.762米)。
1906年鉴11月,日俄战争后,东清铁道南部支路管理权转归日本,南满洲铁道株式会社总社在东京成立。11月11日将宽轨改为窄轨(1.067米)。
1907年3月,南满洲铁道株式会社总社迁至大连。
1907年6月,北洋政府修建的沈山铁路建成通车。
1907年7月1日,日本将南満铁路由窄轨改为标准轨(1.435m)
长图线由吉长线(1912年修建)、吉敦线(1928年修建)、敦图线(1933年修建)三条铁路连成,修建历时23年。
1931年9月18日,夜10时20分南满铁路日本守备队第二大队按照关东军司令部计划,将南满铁路沈阳柳条湖一段路轨炸毁,反诬中国军队破坏铁路,“九一八”事变爆发。
1934年4月,沈吉线由军阀张作霖主持修建完成。
1935年10月31日,长白线修建完成,11月1日运营。
1948年11月,东北解放,成立了沈阳铁路军事管理局。
1949年3月,沈阳铁路军事管理局改为沈阳铁路管理局,下辖长春,丹东两个分局,管辖铁路1120公里。
1950年5月,成立了中苏共管的中长铁路管理局,沈阳铁路局撤消。
1952年12月,中长铁路管理局撤消,成立了哈尔滨铁路局,统管原沈阳局铁路。
1956年1月,成立了沈阳铁路局,下辖沈阳,长春,大连,安东(丹东)四个分局,营业里程为2641公里。
1958年9月10日,沈阳铁路管理局改为沈阳铁路局。
1967年3月,沈阳铁路局实行军事管制。
1968年5月30日,沈阳局成立革委会。
1978年4月,沈阳铁路局革委会撤消,恢复铁路局原建制。
1983年10月1日,锦州,吉林铁路局撤消,并与原齐齐哈尔铁路局白城分局一起合并成立沈阳铁路局,下辖沈阳,大连,丹东,长春,锦州,阜新,通辽,吉林,图们,通化,白城11个分局,管内包括了辽宁,吉林省的全部和内蒙古东北部以及黑龙江,河北的部分地区。营业里程达到了8361公里。
1986年11月,阜新铁路分局撤消,分别并入锦州和通辽分局;12月,白城铁路分局撤消,并入长春分局。
1993年10月,重新组建白城铁路分局。
1995年12月8日,大连铁道有限责任公司正式挂牌成立。
1997年12月31日,丹东铁路分局撤消,并入沈阳分局。
1999年8月27日,沈阳铁路局机关机构改革,撤消运输处,客运处,货运处,成立营销处,车务处,调度指挥中心;撤消生活卫生处,成立卫生处;体改法规处改为政策法规处;成立收入稽查中心,生活服务中心,押运中心,年鉴社等。机关行政机构共设23个处室,精简22•8%。
1999年12月,沈阳铁路局管内铁路营业里程为8798公里,职工346194人,固定资产原值为507.684亿元。净值287亿元。
2000年12月5日,图们分局撤消,并入吉林分局;白城分局撤消,并入长春分局。
2002年6月24日,铁道部下发了《关于沈阳铁路局内部客运公司组建方案的批复》。8月30日,成立了沈阳铁路局客运公司成立大会,9月25日,召开了各分局客运公司成立大会。全局客运公司从2003年1月1日正式独立运作。
2003年8月,调整局机关部分处室部委机构,撤销车务处、营销处、调度指挥中心机构编制,成立运输处、货运营销管理处,客运公司对内称客运事业部。
2005年3月18日,铁道部决定撤消铁路分局,实行路局直管站段体制。