Thành Mục Mã nằm trên địa phận xã Gia Cung (nay là pháp đài thị xã Cao Bằng) có núi đất cao liền với Mục Mã, là thế đất rất hiểm yếu, thành đắp bằng đất, bên ngoài có hàng rào bằng gỗ kết lại. Đến cuối năm Đinh Mão, sau khi dẹp xong nhà Mạc, triều đình thấy binh sỹ ở đất Cao Bình quá đông, mất vệ sinh, sinh ra dịch bệnh nên đã giao cho tướng Hoàng Triều Hoa dời trấn lỵ từ Cao Bình về Mục Mã là nơi chăn ngựa của nhà Mạc, nơi có 3 sông vây bọc, 4 núi chầu quanh. Tam giang, tứ trụ là đất vượng khí hun đúc nên. Tướng Hoàng Triều Ninh giữ chức thống lĩnh quân cơ từ thành Nà Lữ chuyển về thành Mục Mã giao cho Quỳ Quận Công đốc xuất một vạn quân xây lại thành. Cổng thành là một thành đất liên hoàn với phố Lương Mã và dựng một văn miếu ở đấy. Đến năm Tân Dậu niên hiệu Cảnh Hưng thời Tây Sơn, trấn thủ là Hội Vũ Hầu dựng thêm một đồn trước thành. Đến năm Quý Hợi niên hiệu Gia Long thứ hai (1804), trấn thủ là Tiến Ngọc Hầu lệnh cho xây thành cao lên tam cấp. Đốc chấn Nguyên Duy Nhị thời Lê Cảnh Hưng đặt là phố Đông Tân, đầu năm Giáp Thìn thời Tây Sơn, trấn thủ Hào Quang Hầu mới gọi là phố Lương Mã (phố cũ). Sách Khâm Định Đại Nam hội diễn sử lê và sách Đại Nam nhất thống trí nói về sửa sang thành Mục Mã chu vi 180 trượng (720m) cao 8 thước năm tấc (3,4m), hào rộng 2 trượng (8m) sâu 7 thước (2,8m), mặt trước xây gạch, mặt phải, mặt trái, mặt sau đắp đất, có 3 cổng, một kỳ đài đắp, năm Minh Mạng thứ 5 (1824) trong thành còn xây 3 kho thóc, vào năm Thiên Trị thứ 3 (1843), xây thêm kho thuốc súng, vào năm Thiên Trị thứ 6 (1846) xây kho binh khí, kho đạn.

Từ thời Lê Mạc phân tranh, phân quyền cát cứ, thời Tây Sơn, thời Nguyễn, thành Mục Mã luôn luôn biến loạn. Đời vua Minh Mạng giặc dã nổi lên cướp phá thành. Có một trận được ghi vào sử sách, có thơ, ký, câu đối, văn tế… còn lưu lại trong cuốn “Cao Bằng ký lược” của tác giả Cao Phiên Phạm An Phủ soạn.
Thời vua Minh Mạng, nbày mùng 2 tháng 7 năm Quý Tỵ (1833) tri châu Bảo Lạc Nông Văn Nân khởi nghĩa ở Vân Trung chống lại triều đình hà khắc. Quân Nông Văn Nân đánh chiếm Cao Bằng, Lạng Sơn, Tuyên Quang, Thái Nguyên. Ngày 02/10/1833, tướng của Nông Văn Vân là Nguyễn Hữu Giám, Nguyễn Hữu Cận, Nguyễn Hữu Mão, Quang Ngọc đánh chiếm thành Mục Mã. Thành bị vây 1 tháng, hết lương thực, thuôc súng, viện binh bị chặn đánh không ứng cứu được; 3 quan đầu tỉnh là Bố tránh Bùi Tăng Huy, An sát Phạm Bá Trạc, Lãnh binh Phạm Văn Lưu bàn với nhau cùng đều tự vẫn để tỏ lòng chung với vua Phạm Bá Trạc tự chôn sống mình, Bùi Tăng Huy và Phạm Văn Lưu thắt cổ tự tử ngay trong thành Mục Mã. Vua Minh Mạng cho lập đền thờ gọi là đền Tam Trung (phường Sông Bằng). Có nhiều câu đối thơ, trong đó có câu:

"Tuyệt bút một chương trung lẫn hiếu,

Hy sinh ba vị chết vẫn còn."