Lịch sử mảnh đất Xứ Thanh bên dòng sông Mã hiền hòa đã ghi nhận mảnh rất nhiều tên gọi khác nhau qua các thời kỳ lịch sử: Châu Ái, trấn Thanh Đô, thừa tuyên Thanh Hóa, Thanh Hoa, và rồi lại Thanh Hóa. Đến Thành phố Thanh Hóa hôm nay, chúng ta sẽ được biết đến rất nhiều những địa danh, những tên gọi mang đậm dấu ấn của một tòa thành cũ: Bến Ngự, cửa Tả, cửa Hữu, Đông Phố, Nam Phố, Thọ Hạc, Hạc Thành, Cốc Hạ, Hàng Đồng, Hàng Than, Hàng Hương, kênh nhà Lê...
Trong hệ thống thành quách Việt Nam, thành Tư Phố - Thủ phủ của xứ Thanh xưa (ở làng Giàng xã Thiệu Dương, huyện Thiệu Hoá, Thanh Hoá) có bề dầy năm tháng chỉ đứng sau Loa Thành nơi An Dương Vương định đô đời Chu Noãn Vương Tần Thuỷ Hoàng (Năm 257 tr CN). Theo sách Thuỷ Kinh Chú, một bộ sách có ghi chép về địa lý thời ấy trong thư tịch cổ Trung Quốc thì từ thành Tư Phố xuất hiện từ năm Nguyên Đỉnh thứ 6. Đối chiếu với niên biểu, Nguyên Đỉnh là niên hiệu của Vương triều Tây Hán, đời Hán Vũ Đế, năm thứ 6 là năm 116 Tr CN. Cũng giống như Loa Thành nơi khởi đầu cho những mạch nguồn truyền thuyết chảy cùng thời gian lưu vào hậu thế. Thành Tư Phố cũng in dấu ấn vào thời gian nhiều câu chuyện bi hùng, nhiều truyền thuyết lấp lánh các ánh vàng lịch sử.
Cũng theo sách Thuỷ Kinh Chú thì “Năm kiến Vũ thứ 19 tháng 10, Mã Viện vào quận Cửu Chân ở phương nam… Đến huyện Cư Phong, tướng giặc không đầu hàng đều chém mấy chục đến mấy trăm người… Cửu Chân bèn yên”. Đó là cuộc viễn chinh của Mã Viện. Mùa hè năm 43 Mã Viện kéo quân đến Lãng Bạc. Đạo quân của hai Bà (Trưng Trắc, Trưng Nhị) chặn giặc không thành, tan vỡ. Một cánh quân Cửu Chân do Chu Bá, Đô Đương chỉ huy lui về thành Tư Phố tiếp tục kháng chiến. Tháng 11 năm 43 Mã Viện cùng 2000 chiếc thuyền theo đường thuỷ tiến đánh Cửu Chân. Chúng chỉ đoạt được thành Tư Phố khi “tướng giặc không hàng, đều chém đến mấy trăm người”. Thành Tư Phố đã ngân lên khúc bi hùng ca đầu tiên trong lịch sử chống giặc ngoại xâm của người xứ Thanh như thế. Hai ngàn năm, trải qua bao vương triều thành Tư Phố thiêm thiếp trong đêm dài Bắc Thuộc. Năm 1804 (năm Gia Long thứ 3) Thế tổ Nguyễn Phúc Ánh quyết định rời thành Tư Phố. Xã Thọ Hạc được chọn đặt Trấn lị của Trấn Thanh Hoa với tên mới: Hạc Thành (Thành chim Hạc).
Truyền thuyết kể: Sau khi đánh bại nhà Tây Sơn, tháng 6 năm Nhâm Tuất 1802 Nguyễn Ánh lên ngôi vua lập ra vương triều Nguyễn (Triều đại phong kiến quân chủ cuối cùng trong lịch sử Trung đại Việt Nam) lòng vẫn không yên với đất Bắc Hà, nơi có nhiều cựu thần nhà Lê. Sau ngày đăng quang vua Gia Long bàn bạc chia đặt quan chức để cai quản 11 trấn Bắc Thành, bàn phép khoa cử thu hút nhân tài, vỗ về sĩ phu đất Bắc. Trước khi xa giá hồi loan, ông về Nguyên miếu ở trong thành Triệu Tường, thuộc địa phận Quý Hương, Quý Huyện (Quý Hương: Gia Miêu ngoại trung. Quý Huyện: tức huyện Tống Sơn, Hà Trung, Thanh Hoá ngày nay) bái yết tiên tổ. Đêm ấy, một đêm mùa thu se lạnh nơi huyện Tống Sơn. Mưa thu như lưới giăng câu móc ngoài cửa sổ, gió núi ràn rạt thổi về nhà vua bồn chồn không yên. Một suy nghĩ bám riết trong ông: Chọn địa điểm nào để rời thành Tư Phố đặt trấn lị Cho Trấn Thanh Hoa? Đất Thanh Hoá là đất thang mộc, núi sông ngùn ngụt linh khí. Phía Tây bắc Trấn có đất An Tôn, có thành Tây Đô nhưng là nơi đất chật hẹp, hẻo lánh, nơi đầu non cuối nước, hợp với loạn mà không hợp với trị. Phía tây nam có đất Đông phố (huyện Đông Sơn) nhà Tuỳ (589) đã từng chọn đặt quận trị, phía Đông Bắc có đất Duy Tinh (huyện Hậu Lộc) đời Lý (1012) chuyển về nhưng đều không có gốc vững bền. Thao thức mãi đến tận canh ba nhà vua mệt mỏi, chập chờn đi vào giấc ngủ. Đột nhiên cửa hành cung mở xịch. Một người, mặt mũi khôi ngô, tay dài quá gối, mình như mình hạc, vóc như vóc tiên, toàn thân áo quần trắng muốt tiến đến sụp lạy trước mặt vua tâu: “Biết Bệ hạ đang trăn trở tìm địa điểm dời thành Tư Phố, Thần Bạch Hạc phái tôi đến giúp bệ hạ việc này. Ngày mai khoảng giữa giờ Thìn xin bệ hạ theo tôi định đất. Đó là nơi bền vững muôn đời, loạn có thể giữ, bình có thể trị, dẫu sau này có lần đổ nát nhưng lại hoàn như châu về Hợp Phố”. Nhà vua toan hỏi thì người đó chẳng thấy đâu chỉ thấy một ánh hào quang trắng mềm mại tựa ánh trăng ngàn uyển chuyển bay qua rèm cửa. Dìu dịu mùi hương thơm kỳ lạ lan toả khắp nhà. Giật mình tỉnh giấc nhà vua mới biết mình vừa qua một giấc chiêm bao. Nửa mừng nửa sợ nhà vua tự hỏi: Thần Bạch Hạc là vị thần nào, phải chăng đây là thần Chim Lạc, cha ông xưa đã thờ là Chim Tổ, loài linh điểu giang cánh bay trên trống đồng? Như vậy linh khí của núi sông này đã giúp ta tìm ra nơi trấn lỵ cho trấn Thanh Hoa. Sáng hôm sau nhà vua kể lại chuyện trong giấc chiêm bao cho các cận thần, truyền lệnh sẵn sàng xe ngựa chờ Thần linh ứng. Nhà vua còn dặn giữa giờ thìn hễ có người mặc áo trắng đến lập tức phải đón vào bái kiến. Chưa đến giờ thìn các quan hầu cận đã dõi mắt chăm chú quan sát những con đường dẫn đến Nguyên miếu. Rồi giờ thìn cũng tới. Những lối mòn thấp thoáng trên rặng núi xa xa vẫn chẳng thấy bóng vị thần hay vị tiên nào xuất hiện. Đúng giữa giờ thìn bỗng từ trên không vang vọng xuống tiếng chim lạ. Nhà vua cùng các quan ngửa mặt trông lên. Một con chim Hạc trắng to lớn khác thường cứ bay lượn trước sân nhà vua ngự như có ý đợi chờ. Nhà vua hiểu ra liền lên xe ngự giá. Chỉ chờ thế chim Hạc kêu to liền mấy tiếng rồi bay trước dẫn đường. Đến một vùng đất mới có rất nhiều đầm nước xanh biếc chim Hạc ngừng cánh bay hạ xuống trước xe nhà vua gật gật đầu. Vua chưa kịp đáp lời cảm tạ thì chim Hạc đã vụt bay sang một đầm nước kế bên, thân hình đột nhiên cứ nhỏ dần nhỏ dần hoà lẫn vào các loài chim khác đang tung tăng bơi lội trên mặt nước. Nhà vua phóng tầm mắt bao quát khắp vùng. Quả là nơi sơn thuỷ hữu tình. Núi sông như đặt bày trên đồng xôi bãi mật. Phía đông có dãy Linh Trường và dãy Trường Lệ làm án. Tả có long sơn long thuỷ, hữu có hổ phục hổ chầu. Đây chính là vùng đất vua trông đợi bấy lâu nay. Vui mừng khôn xiết nhà vua chỉ tay xuống đất dõng dạc bảo các quần thần: Ta sẽ dựng thành ở chính nơi này. Toà thánh đó gọi là thành Chim Hạc.
Một đoạn tường thành cũ của Thành Thọ Hạc
Tháng 5 năm 1804, theo Chỉ dụ của vua Gia Long, Trấn thành Thanh Hóa được dời từ làng Dương Xá (xã Thiệu Dương, huyện Thiệu Hóa) về làng Thọ Hạc (huyện Đông Sơn) để xây dựng Trấn lỵ. Đầu năm 1828 quân dân Thanh Hóa bắt đầu xây dựng Trấn thành. Trấn thành Thanh Hóa hình lục lăng, có chu vi 630 trượng (gần 2,6 km), cao 1 trượng (4 m), có hào bao quanh mặt ngoài, Thành mở 4 cửa: Cửa tiền phía Nam, cửa hậu phía Bắc, cửa tả phía Đông Nam, cửa hữu phía Tây Nam. Trong Thành là nơi ăn ở vị trí của các quan trị đầu tỉnh. Ngoài thành các chợ, các phố dần định hình. Chợ có chợ Vườn Hoa lớn nhất tỉnh, các phố mang tên nghề như phố Hàng Đồng chuyên bán đồng, phố Hàng Hương chuyên sản xuất và buôn bán hương…
Tháng 11 - 1885 quân xâm lược Pháp mới đổ bộ vào Thanh Hóa nói chung và tỉnh lỵ Thanh Hóa nói riêng. Để nắm toàn quyền cai trị tỉnh lỵ, ngày 22 tháng 7 năm 1889, vua Thành Thái ký đạo dụ thành lập thị xã Thanh Hóa bao gồm 7 làng: Đức Thọ Vạn, Cẩm Bào Nội, Cốc Hạ, Phủ Cốc (thuộc Tổng Bố Đức); Thọ Hạc, Đông Phố, Nam Phố (thuộc Tổng Thọ Hạc)
Năm 1918, thị xã Thanh Hóa tổ chức thành 10 phường: Tả Môn (cửa Tả), Bắc Môn (cửa Hậu), Nam Môn (cửa Tiền), Đông Lạc, phường Thành Thi, phường Nam Lý, phường Phú Cốc, phường Vạn Trường, phường Bào Giang, phường Đức Thọ (Lò Chum) (2). Ngày 31 tháng 5 năm 1929, toàn quyền Đông Dương ký Nghị định nâng cấp thị xã Thanh Hóa lên thành phố Thanh Hóa. Bốn tháng sau, ngày 11 tháng 9 năm 1929, Đốc lý thành phố điều chỉnh lại địa giới hành chính: Phía Bắc giáp làng Thọ Hạc, phía Nam giáp làng Mật Sơn, phía Đông giáp Bến Ngự và phía Tây giáp Phủ Đông Sơn. Cũng theo Nghị định trên, kể từ ngày 01 tháng 01 năm 1930, thành phố được chia thánh 6 đơn vị hành chính, từ phường Đệ nhất đến Đệ lục.
Ngày 24 tháng 11 năm 1946, Chủ tịch Hồ Chí Minh ký sắc lệnh số 11/SL quy định những thành phố thuộc tỉnh gọi là thị xã. Thành phố Thanh Hóa, mặc nhiên trở thành thị xã của tỉnh Thanh Hóa.
Ngày 16 tháng 3 năm 1963, Chính phủ nước Việt Nam dân chủ cộng hòa quyết định sát nhập xã Đông Giang (gồm 3 làng Nghĩa Phương, Đông Sơn và Nam Ngạn) thuộc huyện Đông Sơn và xóm Núi xã Hoằng Long, huyện Hoằng Hóa vào thị xã. Ngày 28 tháng 8 năm 1971, Chính phủ ban hành Nghị định số 226/TTg sát nhập xã Đông Vệ, Đông Hương, Đông Hải thuộc huyện Đông Sơn và xã Quảng Thắng thuộc huyện Quảng Xương vào thị xã.
Ngày 05 tháng 5 năm 1991, Hội đồng Bộ trưởng ra Quyết định số 132/BĐBT về phân loại đô thị, thị xã Thanh Hóa được xếp vào loại đô thị loại 4. Ngày 14 tháng 8 năm 1993, Bộ trưởng Bộ Xây dựng ra Quyết định số 214 BXD/ĐT công nhận thị xã Thanh Hóa là đô thị loại 3.
Ngày 01 tháng 5 năm 1994, Thủ tướng Chính phủ ký Nghị định 37/CP thành lập thành phố Thanh Hóa, thuộc tỉnh Thanh Hóa trên cơ sở địa giới, diện tích và dân số của thị xã Thanh Hóa.
Ngày 28 tháng 6 năm 1994, Chính phủ ra Nghị định số 55/CP thành lập phường Đông Thọ, phường Đông Vệ và chia phường Nam Ngạn thành 2 phường Trường Thi và Nam Ngạn.
Ngày 6 tháng 12 năm 1995, Chính phủ ra Nghị định số 85/CP điều chỉnh địa giới thành phố Thanh Hóa, sáp nhập xã Đông Cương thuộc huyện Đông Sơn, xã Quảng Thành, Quảng Hưng và một phần đất của xã Quảng Thịnh thuộc huyện Quảng Xương vào thành phố.
Năm 2004, thành phố Thanh Hóa được Thủ tướng Chính phủ công nhận là đô thị loại II (theo Quyết định số 72/2004/QĐ-TTg ngày 29 tháng 4 năm 2004)
Năm 2012, thành phố Thanh Hoá được mở rộng thêm 19 xã, thị trấn thuộc huyện Hoằng Hoá (gồm các xã Hoằng Lý, Hoằng Long, Hoằng Anh, Hoằng Quang, Hoằng Đại và thị trấn Tào Xuyên); huyện Đông Sơn (gồm các xã Đông Lĩnh, Đông Tân, Đông Hưng, Đông Vinh và thị trấn Nhồi); huyện Thiệu Hoá (gồm các xã Thiệu Dương, Thiệu Khánh, Thiệu Vân) và huyện Quảng Xương (gồm các xã Quảng Thịnh, Quảng Đông, Quảng Phú, Quảng Tâm, Quảng Cát). Trong đó thị trấn Tào Xuyên đổi thành phường Tào Xuyên, thị trấn Nhồi đổi thành phường An Hoạch.
Tháng 4 năm 2014, thành phố Thanh Hóa được Thủ tướng Chính phủ công nhận là đô thị loại I trực thuộc tỉnh.
PV