Đống Lim gắn liền với huyền tích xây dựng cung cũ Cổ Bi ở cách đó không xa, truyền thuyết dân gian vẫn lưu giữ cách lý giải độc đáo về tên gọi trên. Tục truyền, hồi đó, trong một đêm, song song với xây dựng cầu đá và 95 gò đống, cung điện ở Cổ Bi, thì các Tiên nữ cũng khẩn trương xây dựng ngôi chùa. Công trình đang được tiến hành thì Thần bản thổ của khu vực này đã ngăn việc xây dựng bằng cách giả tiếng gà gáy để các Tiên nữ tưởng trời đã sáng mà bay về trời. Sáng hôm sau, mọi người quanh vùng kéo đến thì chỉ thấy 4 cột gỗ lim to được dựng, một bè gỗ lim lớn dưới sông Nghĩa Trụ. Nhân dân các làng tranh nhau kéo gỗ nhưng không chuyển, riêng chỉ người thôn Nha mới kéo nổi và dựng tiếp được chùa. Từ đó, chùa mang tên Cổ Linh (tên xã Long Biên trước đây) hay còn gọi là chùa Nha, chùa Đống Lim. Từ truyền thuyết, cũng như các tài liệu hiện còn cho thấy nhiều khả năng niên đại xây dựng của di tích là đầu thế kỷ XVII, dưới thời Lê Trịnh, cuối thế kỷ chùa đã trở thành một thắng cảnh lớn, được miêu tả trong Thượng Kinh ký sự của Hải Thượng Lãn Ông Lê Hữu Trác là “Cảnh chùa miếu huy hoàng…”.
Cùng vào thời gian này, nhiều pho tượng đẹp của chùa đã ra đời. Đến đầu thời Nguyễn, làng đúc quả chuông lớn “Cổ Linh tự chung”, sau đó Tiền đường, Tam bảo, Nhà Tổ và Nhà Mẫu được dân làng cùng thập phương cung tiến để trùng tu, mở rộng. Kiến trúc ngôi chùa hiện nay mang nhiều dấu ấn của những lần tu sửa thời Nguyễn. Ngay từ khi ra đời và trong suốt quá trình tồn tại, ngôi chùa luôn gắn bó mật thiết với từng chặng của đường lịch sử dân tộc. Trong cuộc kháng chiến chống Pháp (1946-1954), trước sự phát triển của phong trào chiến tranh du kích, thực dân Pháp đã phá hủy nhà Giải vũ của chùa để xây lô cốt bảo vệ tuyến đường sắt Hà Nội – Hải Phòng.
Chùa Cổ Linh được xây dựng trên một khu đất cao, rộng rãi và bằng phẳng. Dưới những tán cây lưu niên là khu chùa chính, Nhà Mẫu và Nhà Tổ, quy hoạch gọn gàng trong một khuôn viên khép kín tạo nên vẻ thâm nghiêm. Mở đầu trên đường vào là một Tam quan mới xây bề thế, bên phải là khu vườn tháp rộng với hàng chục tòa tháp mộ cổ cao thấp khác nhau, dấu tích thời kỳ hưng thịnh của ngôi chùa.
Chùa chính quay hướng Bắc, trông ra quốc lộ số 5, có kết cấu hình chữ Đinh gồm Tiền đường và Thượng điện. Tiền đường 5 gian 2 dĩ, xây kiểu tường hồi bít đốc tay ngai, mái lợp ngói ta. 6 bộ vì đỡ mái được làm theo kiểu “chồng rường giá chiêng, hạ kẻ”, các cột cái có đường kính 50cm, 3 bộ vì của Thượng điện được làm kiểu chồng rường tựa trên 2 hàng chân cột lớn. Liên kết các vì là hệ thống xà đai thượng hạ chạy khắp 3 gian nhà. Khu nhà Mẫu, Nhà Tổ nằm phía sau chùa chính, quy mô vừa phải, hài hòa trong tổng thể chùa.
Giá trị nghệ thuật của di tích tập trung chủ yếu trên kiến trúc chùa Cổ Linh và hệ thống tượng tròn. Các đồ án hoa văn truyền thống như rồng lá, hoa văn thực vật, vân mây, đài sen, lá ba chẽ được chạm nổi bong kênh trên các câu đầu, rường, kẻ, bẩy hiên. Đặc biệt, trên 2 bức ván đó là các đề tài rồng mây, rồng có đầu nổi cao, thân nhỏ uốn khúc nhiều lớp, ẩn hiện trong những dải mây cuộn. Niên đại tạo tác của 2 bức chạm này không sớm nhưng có giá trị thẩm mỹ cao, góp phần tạo nên vẻ đẹp truyền thống của ngôi chùa. Điêu khắc nghệ thuật của chùa Cổ Linh được thể hiện trong hệ thống tượng tròn, tượng tuy không nhiều, song được tạo tác hoàn chỉnh, công phu mang vẻ đẹp sinh động của nghệ thuật điêu khắc cổ Việt Nam thời kỳ cuối Lê đầu Nguyễn. Hệ thống tượng tròn của chùa với gần 30 pho tượng các loại, trong đó, có những pho tượng được tạo tác dưới thời Lê mạt (thể kỷ XVIII) như bộ Phật Tam thế, bộ Di Đà Tam tôn, Quan Âm Chuẩn Đề, còn lại là các pho được thể hiện mang đặc trưng nghệ thuật điêu khắc thời Nguyễn, thế kỷ XIX. Có những niên đại tạo tác sớm muộn khác nhau, song những pho tượng của chùa đều mang nét chung độc đáo của nghệ thuật điêu khắc dân gian. Ngoài hệ thống tượng tròn, chùa Cổ Linh còn bảo lưu được một số di vật quý như quả chuông đồng lớn “Cổ Linh tự chung” có niên đại đầu thế kỷ XIX và nhiều hoành phi, câu đối cùng những vật có giá trị khác.
Trải qua thời gian, quá trình đô thị hóa, ngôi chùa vẫn gắn bó với đời sống sinh hoạt tâm linh của cộng đồng cư dân địa phương. Giá trị lịch sử nghệ thuật của ngôi chùa ngày càng được khẳng định và trân trọng. Cùng với đình Nha, chùa Nha đã làm nên một quần thể di tích tôn giáo tín ngưỡng, góp phần kiến tạo và giữ gìn một nét đẹp trong văn hóa cổ truyền Việt Nam.