Theo truyền ngôn, năm Mậu Tuất (1288) Hưng Đạo Vương khi đến vùng An Dương để nghiên cứu trận thuỷ chiến tiêu diệt đoàn thuyền Ô Mã Nhi rút chạy qua cửa Bạch Đằng, có đội hỏa đầu quân ở chùa Linh Độ Tự lo việc phục dịch ăn uống cho bộ chỉ huy chiến dịch. Chùa vốn là nơi am thanh cảnh vắng, khi đội hỏa đầu quân đến đóng, bếp luồn đỏ lửa. Do đó có thêm tên dân dã để nhớ đến kỷ niệm ngày Đức thánh Trần trú quân ở đây.
Sau khi Trần Hưng Đạo qua đời, dân làm hai ngôi miếu ở hai bên chùa để thờ ngài và các bộ tướng thân tín là các con trai và con rể, tức Điện soái Phạm Ngũ Lão, đó chính là ngôi chùa Đỏ tọa lạc tại địa chỉ đường Lê Lai, phường Má Chai, quận Ngô Quyền, thành phố Hải Phòng ngày nay.
