Theo sự tích thì ngôi đền đã có từ thời vua Hùng Duệ Vương, tức đã trên 2000 năm. Ngôi đền này xưa có tên Hoa Đào Trang.
Trong khu quần thể tâm linh đền Đồng Bằng có đến 7 ngôi đền. Trong đó đền Đồng Bằng là đến chính và còn có 5 ngôi đền khác: Đền Sinh, Đền Quan Đệ Nhị, Đền Quan Đệ Nhất, Đền quan Đệ Tam, Đền Quan Điều Thất, Đền quan Đệ Bát.
Cổng đền Đồng Bằng
Tục truyền, vào đời Vua Hùng Vương thứ 18, nước nhà bị ngoại bang xâm lấn, Long Cung Hoàng Thái Tử (Giao Long - con của Lạc Long Quân và người thiếp Ngọc Nữ) đầu thai vào một gia đình vùng cửa sông Vĩnh thuộc Trang Hoa Đào, đất Việt (An Lễ, Quỳnh Phụ bây giờ),giúp vua đánh giặc. Ngài cùng 2 em, 10 tướng (Quan Lớn thượng, Quan Đệ Tam, Quan Đệ Tứ…Quan Điều Thất (Hoàng Mười ),quân sư quê ở Nuồi (Tứ Kỳ - Hải Dương),28 vị nội tướng và binh sĩ, chỉ trong 3 ngày xuất quân đã đánh tan giặc trên 8 cửa biển nước Nam. Từ đó, ngài có tên là Vĩnh Công (Trọng nhân phát tích trên sông Vĩnh).
Sau chiến thắng, Hùng Duệ Vương triệu Vĩnh Công về triều phong là "Vĩnh Công Nhạc phủ Thượng đẳng thần". Ngài xin về quê trông nom thân mẫu, khai khẩn vùng duyên hải, chiêu dân lập ấp, giúp vua Hùng giữ yên 8 cửa biển Lạc Việt. 10 tướng theo Ngài về Hoa Đào Trang. Riêng Quan Điều Thất về trời ngay sau khi thắng giặc. Vĩnh Công thương xót cho lập bàn thờ ngay tại Dinh Công Đồng là nơi ngài cùng chư tướng bàn việc (đó chính là Đền thờ quan Điều Thất ngày nay, thường gọi là Đền Công Đồng). Quan lớn Đệ Tam được phân công giữ yên vùng duyên hải từ sông Cái lên hết biên giới phía Bắc Lạc Việt. Quan lớn Đệ thập được tỵ nhậm tại Cửu Chân, Quan Đệ tứ được phân công khai khẩn vùng Bắc Sơn Nam…
Có 5 vị nội tướng được Vĩnh Công sai khai khẩn chăn dân, lập ấp tại Hoa Đào trang (sau chính là 5 vị thành hoàng nổi tiếng linh ứng, đã có công âm phù Trưng Vương đánh thắng quân Tô Định)…Vua Hùng trao Vĩnh Công quản lý miền duyên hải Lạc Việt lấy tên là Tây Đô. Định kỳ hàng năm, nhân ngày đại thắng quân phương Bắc trên 8 cửa biển, Vĩnh công triệu chư tướng về tề tựu tại Hoa Đào trang (đất An Lễ bây giờ) tổ chức thi đấu vật, thi võ, bơi thuyền, giữa đội thuyền bản hạt và thuyền của các tướng, thuyền của quân sư Nuồi, để ôn lại chiến thắng, tập dượt phòng thủ và luyện quân sẵn sàng ứng phó mọi biến cố... (lệ thi bơi trải có từ đó).
Ngày 25 tháng 8 âm lịch, năm Bính Dần, Vĩnh Công thác về trời. Để ghi nhớ công ơn ngài, người dân trong vùng tôn ngài là “Vua cha - Bát Hải Đại Vương”, coi ngài như cha mẹ của dân. Vua Hùng thương xót, ban phong mỹ hiệu: "Trấn Tây An Tam kỳ linh ứng Đại Vương" cho tu sửa dinh thất của Vĩnh công thành miếu điện thờ tự hương hoả cho Vĩnh công mãi mãi... Từ đó, nhân ngày giỗ Vĩnh Công, các tướng lại tề tựu tại Hoa Đào trang, dâng hương và tổ chức các hình thức kỷ niệm ngày đại thắng như trước đây ... Lâu dần thành lệ Hội tháng 8 âm lịch mà truyền đến ngày nay.
Các tướng của Vĩnh Công sau khi mất đều được lập đền thờ, được các triều đại sau sắc phong tôn vinh, kính trọng. Tại đất Đào Động có Đền thờ Quan lớn Thượng, Quan lớn đệ Nhị, Quan lớn Đệ Tam, Quan lớn Điều Thất, Quan lớn Đệ Bát, tĩnh Quan lớn Thượng, tĩnh Quan Đệ Tứ, đều được tái tạo dựng trên nền cổ tự. Quan Đệ Ngũ thờ tại Đình Giới Phúc, tĩnh Quan Đệ Lục (Miếu Giáp Nhị) đã bị thực dân Pháp phá huỷ. Quan Đệ Tam còn được thờ ở Đền Lảnh Giang (Hưng Yên),Quan Đệ Tứ đền thờ chính ở Vĩnh Bảo - Hải Phòng. Quan Đệ Ngũ có đền thờ ở bến đò Chanh - Hải Dương, Quan Điều Thất có Đền ở Bảo Hà - Lào Cai. Quan Đệ Cửu xưa có Đền ở Thanh Hoá, Quan Đệ Thập (Hoàng Mười) có đền ở Nghệ An...
Đền thờ Vĩnh công Đại Vương Bát Hải Động Đình từ xa xưa đã nổi tiếng linh ứng. Các triều đại sau này như Đinh, Lê, Lý, Trần, Lê, Nguyễn... đều tái sắc phong cho ngài. Vĩnh Công được coi là Thượng Đẳng Thần của đất Lạc Việt, Hội tháng 8 âm lịch tại Đền, hội tụ muôn phương dân Việt về chiêm bái lễ cầu. Câu thành ngữ dân gian: Tháng 8 giỗ Cha, tháng 3 giỗ Mẹ chính là để chỉ Hội tháng 8 ở Đền Đồng Bằng. Đây được coi là nơi "đi trình về tạ" của các bản Hội tín ngưỡng trong toàn quốc từ xa xưa.
Dựa vào truyền thuyết, Vĩnh Công chính là Thái tử Giao Long (em cùng cha khác mẹ với vua Hùng Vương 18) sau khi hóa thần nhưng vẫn cực kỳ linh hiển phù trợ dân đất Việt, vì thế dân tôn sùng gọi ngài là Đức Vua. Đền Vĩnh Cung vì vậy còn gọi là đền Đức Vua. Mặt khác vì ông đã có công đánh giặc, giúp vua giữ yên 8 cửa biển Lạc Việt nên dân gian còn gọi đền Vĩnh Công bằng tên gọi Đền Đức Vua Bát Hải.
Trong kháng chiến chống quân Nguyên Mông, đất Đào Động Hoa Đào trang xưa ( An Lễ - Quỳnh Phụ bây giờ ) là nơi hội quân của nhà Trần, chuẩn bị cho đại chiến Bạch Đằng... Đền Quan Đệ Tam, Đền Quan Thượng ở phía bắc đất Đào Động (gần Đống Đà) tương truyền là Đại bản doanh của danh tướng Yết Kiêu. Trên vùng chợ Đồng Bằng hiện tại, thời Trần gọi là Thôn Đông, có các di tích: Đình Đông (Đình Tháng 8) thờ Thành Hoàng Đường Đô Giám (tuỳ tướng của Vĩnh Công ),có Quán Trải (bảo quản Trải lớn của 6 Giáp, để thi bơi trong Hội tháng 8),Miếu Cảnh Am, Miếu Thu Phan. Thôn Đoài có Đền Quan Đệ Nhị, chùa Tây, tĩnh Quan Đệ Tứ, tĩnh Quan Đệ Lục (Miếu Giáp Nhị - Thời Trần, đây là nơi tuyển quân Thánh Dực). Thôn Lãng có Đình Lãng thờ Thành Hoàng "Ba Lãng Hãn Vệ Đại Vương" (Thời Trần, đây là bản doanh của Phò mã Nguyễn Chế Nghĩa). Thôn Dất, cách Đền Đức Vua 600 m, là Đình Dất, thờ thân Mẫu của Vĩnh Công xưa (Đời Trần, Đình Dất là bản doanh của Điện Tiền Đô uý Phạm Ngũ Lão). Đền Quan Đệ Bát cổ, là nơi đóng quân của danh tướng Dã tượng và thớt Voi chiến lừng danh của Trần Hưng Đạo. Đền Công Đồng thờ Quan lớn Điều Thất từ thời Hùng Vương (Đời Trần là dinh quân của Danh tướng Trần Quốc Tảng - con trai thứ 3 Trần Hưng Đạo). Ông đã cùng Trần Khánh Dư chặn đánh giặc ở cửa biển Vân Đồn. Khi tử trận, ông được lập đền thờ tại Cửa Ông (danh từ Ông là cách gọi tôn trọng Trần Quốc Tảng).
Phía chính bắc đền Đồng Bằng là đống Thần Đồng Hưng thờ 1 trong 5 vị Thành hoàng đã giúp hai Bà Trưng đánh thắng quân Tô Định. Trước ngày tiến quân ra Bạch Đằng cự giặc, Trần Hưng Đạo làm lễ dâng hương tại Đền Đức Vua, Đền Quan lớn Đệ Tam, lập Đàn cầu Bách Thần đất Việt phù trợ rồi ban lệnh xuất quân... Sau chiến thắng Bạch Đằng, Hưng Đạo Vương lại về tế tạ tại Đền. Khi ông mất, bài vị của ông được lập và thờ cạnh bài vị Vĩnh Công tại cung Cấm trong Đền Đồng Bằng.
Sau 3 lần đại thắng quân Nguyên Mông nhà Trần đã đầu tư công sức, tiền của để tôn tạo Cửa Đền. Năm Trùng Hưng thứ 4 (1288),vua Trần Nhân Tông tái phong mỹ tự cho Vĩnh Công, cho phép mở mang tu bổ đền phủ, tương truyền mở rộng đến cung đệ nhị bây giờ. Dưới thời Tiền Lê, Đền được xây dựng, mở rộng thành 5 công (lấy số 5 của ngũ hành để ngầm chỉ sự bao quát càn khôn),4 ban thờ Công Đồng khang trang, hoành tráng và được liệt vào tứ cố cảnh của nước Việt (Đào Động, Lộng Khê, Tô Đê, A Sào).
Tọa lạc trên khuôn viên rộng 11.000 m2, Đền Đồng Bằng là một quần thể rộng lớn, bao gồm hệ thống các đền, miếu, am, tháp, gọi chung là 6 phủ: 1 đền chính (Đền Đức Vua) và 5 đền khác là đền Sinh, quan Đệ Nhị, quan Đệ Tam, quan Điều, quan Đệ Bát.
Đền Đồng Bằng là một công trình kiến trúc đồ sộ với tầng tầng, lớp lớp các cung của 13 tòa, 66 gian liên hoàn khép kín với các nét trạm trổ tinh vi, hàng trăm câu đối đại tự sơn son thiếp vàng. Theo thuyết phong thủy, Đền tọa lạc trên thế đất đẹp cát vượng, hổ chầu, lăng tụ biểu tượng cho sự vững bền và hưng thịnh. Cổng Đền kiến trúc theo kiểu Đại Vương Tam Tọa Vọng Lâu đời Nguyễn với 3 cửa, cửa Trung môn là chính môn to rộng chỉ mở những ngày Đại lễ, tả hữu môn được mở thường nhật để khách vào Đền. Lầu trên của tòa cổng chính gọi là Lầu Kính Thiên viết 4 chữ: Bát Hải Động Đình khổ lớn. Bước qua cổng tam quan là nơi tổ chức Đại lễ tế Công Đồng cho những ngày lễ trọng. Chính giữa Cung Đệ Tứlà tấm Hoành phi cỡ lớn đề 3 chữ : Phúc, Du, Đồng. Tiếp sau là Cung Đệ Tam, Đệ Nhị với lối bài trí, thiết tự phong phú thể hiện sự thanh hư, thoát tục.