城内西北有2座古城址，西为辽金元时期的东胜州城，东为东胜州城的子城。明初筑东胜卫城时，延用了东胜州之"东胜"二字，称东胜卫。"卫"是明朝的军队建制，每个大卫的编制一般是5600人。明朝初年，明太祖朱元璋在中国北部密设卫，建起了329座卫城，东胜卫为其中之一。
东胜卫城也称"黄城"，其东约30公里处的镇虏卫城称"黑城"，又东去30公里处的云川卫城称为"红城"，这些都是明初在我国北部相继建起的卫城。我国传统将青、赤、黄、白、黑五色视为正色，并赋予这五种颜色丰富的文化内涵。"东胜卫故城濒临奔流不息的黄河，又在平原和丘陵的接壤处，水陆交通便利，地理位置重要，对于扼守黄河水道有着十分重要的战略意义。"赵静说。
《明史》记载："洪武二十五年八月，分置东胜左、右、中、前、后五卫，属行都司。洪武二十六年二月，罢中、前、后三卫。"《山西通志》记载："今厅（托克托厅）其左卫地。"至明永乐元年（公元1403年），又撤销了东胜左、右卫。明正统年间（公元1436年-1449年）虽一度复置，但很快又撤销。东胜卫故城共使用30余年。
据史料记载，明世宗嘉靖十年（公元1531年），土默特部阿拉坦汗授命其义子恰台吉驻牧东胜卫。明穆宗隆庆五年（公元1571年），恰台吉被封为百户。因恰台吉亦名脱脱、妥妥，托克托之名由此而来。
东胜州故城出土的元代绿秞力士像。
