Đền Voi Phục được xây dựng vào đời vua Lý Thánh Tông (1054 - 1072), thờ Linh Lang Đại vương - thần Linh Lang, bởi vậy, ngoài cái tên đền Voi Phục, đền còn có tên gọi khác là đền Linh Lang.
Có nhiều truyền thuyết kể về thần Linh Lang. Theo sử sách ghi lại, thần Linh Lang là hoàng tử nhà Lý - Hoằng Chân, con vua Lý Thánh Tông, đã giúp vua cha chống quân xâm lược Tống bên bờ sông Như Nguyệt (sông Cầu) và đã hy sinh tại đó.
Theo thần tích kể rằng, thần Linh Lang (con rồng) là do Bà Hoàng phi họ Nguyễn (vợ Vua Lý Thánh Tông) sinh ra. Khi quân Tống sang xâm lược bờ cõi nước ta, lúc đó Linh Lang đã lớn, có đủ sức khỏe, chàng xin vua cha ban quân và hai thớt voi để đi đánh giặc. Khi voi đến, Linh Lang bắt voi quỳ xuống, voi liền quỳ xuống rồi đưa chàng và các tướng sỹ ra trận. Trong một lần giáp chiến với quân giặc trên phòng tuyến sông Cầu, Linh Lang đã hy sinh.
Để ghi nhớ công lao của hoàng tử, Đức vua Lý Thánh Tông đã sắc phong cho Hoàng tử là Linh Lang Đại vương và cho xây dựng đền thờ và cho tạc hai con voi đá nằm phủ phục trước cửa đền, sau này, dân chúng cầu đảo gọi luôn là đền Voi Phục.
Ngoài truyền thuyết về thần Linh Lang, nơi đây còn in đậm dấu tích lịch sử. Tháng 5/1882, quan tướng của triều đình dưới thời vua Hàm Nghi là Tôn Thất Thuyết đã hội quân với tướng Cờ Đen là Lưu Vĩnh Phúc phục kích quân Pháp tại đây, tiêu diệt hai tên đại tá giặc (quan năm) là Villers và Henri Rivière.
Trải qua bao thăng trầm lịch sử, đền Voi Phục đã bị hư hại nặng. Từ năm 1953 cho tới nay, ngôi đền này đã được trùng tu nhiều lần.
Hiện nay, ở đền Voi Phục, ngoài hai con voi phủ phục ở trước cửa đền, trong đền còn có hai pho tượng đồng; một hòn đá thiêng có vết lõm; câu đối - ca ngợi công đức của vị thần trấn giữ phía tây của Thăng Long – Hà Nội... Đầu năm 1994, nhân dân Thủ Lệ đã quyên góp đúc lại quả chuông với chiều cao 93cm, đường kính miệng 70cm, thân chia 4 múi, mỗi múi có 2 hàng chữ Hán đúc nổi "Tây trấn thượng đẳng".
Hàng năm, để tưởng nhớ thần Linh Lang, cứ đến ngày 9, 10 và 11/2 âm lịch, nhân dân ở đây tổ chức lễ hội đền Voi phục. Đây là hội rước lớn với cờ quạt, chiêng trống, lọng, tàn, tán nối nhau thành hàng dài cùng phường bát âm và đội sênh tiền rất nhộn nhịp.