牡丹江地名是以牡丹江河流而得名。牡丹江在唐代称忽汗河（一作忽汗水）；金代称呼里改江（一作骨乌里改江）；元代称忽尔哈河；明代称胡里改江（又称呼拉哈河、虎尔哈河、胡尔哈河、呼尔哈河、火儿哈河）；清民称虎尔哈或牡丹江。上述出现的名称，大都为音似字异，均为满语“湾曲”的意思（另一种解释为“响水”）。牡丹江河流蜿蜒曲折，流淌于老爷岭的群山之中，故名为牡丹江，含有湾曲的江水之意。最早为站名，后建置市制时取其为地名。
牡丹江市设置较晚。古时沿革不详。最早可追朔到铺设东清铁路时期，当时曾经在东部线（即当时的滨绥线）、牡丹江两岸设置了驿站，名为牡丹江驿。但在同时铺设的图佳线上亦新设置了一个牡丹江驿（别称宁北），故将滨绥线牡丹江驿称为南牡丹江驿。到了康德四年（1937年）在实行第二次地方行政机构改革中，设置了牡丹江市，并在原十四省的基础上，增设了牡丹江省、通化省。牡丹江市为牡丹江省省公署所在地。康德十年（1943年）十月设置了东满总省（包括牡丹江、东安、间岛）和兴安总省（包括兴安东、西、南、北四省），东满总省公署驻牡丹江市。东北光复后，民国三十六年（1947年）六月五日公布东北新省区方案，废除伪省制，划东北为九省。牡丹江市划属松江省所辖，仍为省会所在地。
全国解放后，划东北为三省，牡丹江市又划归黑龙江省所辖。1956年设牡丹江专区，专署驻牡丹江市；原由省直辖的林口、密山、虎林、穆棱（驻八面通镇）、东宁、宁安、尚志、延寿、方正等9县划归牡丹江专区；海林县撤销，并入牡丹江市和林口、宁安2县。1958年原由省直辖的牡丹江、鸡西2市划归牡丹江专署领导；辖2市、9县。1960年撤销虎林县和原属合江专区的饶河县，合并设立虎饶县（驻原虎林县城）；将宁安县划归牡丹江市领导。1962年，恢复海林县（驻海林镇），宁安县仍划归牡丹江专署领导。1964年以密山县和鸡西市各一部分地区设鸡东县（驻鸡东镇）；撤销虎饶县；牡丹江专区辖2市、10县。
1966年牡丹江、鸡西2市改由省直辖。1967年牡丹江市划归牡丹江专署领导。1970年牡丹江专区改称牡丹江地区；尚志、方正、延寿3县划归松花江地区，原属合江地区的虎林县划入牡丹江地区；辖1市、8县。1975年以原东宁县绥芬河镇设立绥芬河市，由牡丹江地区领导；牡丹江地区辖牡丹江、绥芬河2市及林口、东宁、鸡东、穆棱（驻八面通镇）、密山、宁安、虎林、海林等8县。1980年4月15日，黑龙江省人民政府批准设立牡丹江市阳明区。同年，牡丹江市人民政府批准牡丹江市先锋区更名为西安区、东风区更名为东安区。
1983年9月3日，国务院批准撤销牡丹江地区。牡丹江市升格为地级市；将鸡东县划归鸡西市管辖；将海林、林口、宁安、穆林、东宁、虎林、密山七县划归牡丹江市管辖；绥芬河市由黑龙江省直辖。1983年10月8日，黑龙江省人民政府批准绥芬河市由牡丹江市代管。1986年7月1日，国务院批准（国函[1996]85号）设立镜泊湖市（县级），市政府驻渤海镇，以原宁安县的镜泊、杏山2乡，沙兰镇山区（小北湖林场、尔站林场）、以及渤海镇的8个村和1个街道办事处为镜泊湖市的行政区域。1987年11月27日，国务院批准（国函[1997]183号）撤销镜泊湖市，将其行政区域并入宁安县。
1992年7月28日，民政部批复（民行批[1992]90号）撤销海林县，设立海林市。1993年6月14日，国务院批准将牡丹江市的虎林县划归鸡西市管辖。1993年2月12日，民政部批复（民行批[1993]9号）撤销宁安县，设立宁安市。1995年3月7日，民政部批复（民行批[1995]18号）撤销穆棱县，设立穆棱市。 1997年9月30日，国务院批准（国函[1997]90号），撤销牡丹江市郊区；将原郊区的兴隆镇、东村乡划归东安区管辖；将原郊区的温春镇、沿江乡划归西安区管辖；将原郊区的铁岭镇、桦林镇划归阳明区管辖；将原郊区的北安乡、三道乡划归爱民区管辖。
2000年第五次人口普查，牡丹江市常住总人口2684495人，其中，东安区185506人、阳明区163290人、爱民区271779人、西安区186619人、东宁县207012人、林口县418136人、绥芬河市69052人、海林市435677人、宁安市437328人、穆棱市310096人。
2007年7月11日，《黑龙江省民政厅关于调整牡丹江市部分行政区划的批复》（黑民区[2007]77号）：经省政府批准，同意将穆棱市所辖的磨刀石镇整建制划归牡丹江市阳明区管辖。2007年12月19日，《黑龙江省民政厅关于调整牡丹江市部分行政区划的批复》（黑民区[2007]143号）：同意将林口县所辖的五林镇整建制划归牡丹江市阳明区管辖。2009年，《黑龙江省民政厅关于调整牡丹江市部分行政区划的批复》（黑民区[2009]121号）：同意将海林市所辖的海南朝鲜族乡整建制划归牡丹江市西安区管辖（2010年5月正式实施）。
2010年9月2日，《黑龙江省民政厅关于调整牡丹江市部分行政区划的批复》（黑民区[2010]102号）：经省政府同意，将宁安市宁安镇富民村、双龙村、桥头村划归牡丹江市西安区温春镇管辖。（牡丹江市）要将此次行政区划调整和以前批复的穆棱市磨刀石镇、林口县五林镇、海林市海南朝鲜族乡等相关行政区划调整工作统筹安排，抓紧落实有关交界工作，确保2010年10月底之前将已批复的行政区划调整落实到位，并在一定时间内保持行政区划的稳定。
2010年第六次人口普查，牡丹江市常住总人口2798723人，其中，城镇人口1610348人,乡村人口为1188375人；汉族人口2616386人。东安区200160人，阳明区240214人，爱民区275289人，西安区249491人，东宁县200716人，林口县368956人，绥芬河市132315人，海林市400859人，宁安市437452人，穆棱市293271人。
2015年，经国务院批准，民政部（民函[2015]361号）批复同意撤销东宁县，设立县级东宁市，以原东宁县的行政区域为东宁市的行政区域，东宁市人民政府驻东宁镇通政路1号。东宁市由黑龙江省直辖，牡丹江市代管。