Nhà lao này được xây dựng từ thời Pháp, thuộc xóm Cây Dừa trước đây nên mới có tên gọi như vậy. Thời Việt Nam Cộng Hoà, nhà lao Cây Dừa được mở rộng trở thành trại giam lớn nhất đương thời với tên gọi là Trại giam tù binh chiến tranh Phú Quốc hay Trại giam tù binh Cộng sản Phú Quốc.
Khu di tích ngày nay không rộng, nằm trên khu vực chính nhà lao cũ, có nhà trưng bày hiện vật xây hai tầng và khu trưng bày ngoài trời những hiện vật nguyên gốc và hầu như nguyên vị trí. Nhà lao Cây Dừa được công nhận là di tích lịch sử năm 1996 và bắt đầu mở cửa đón du khách đến tham quan. Nhà lao Cây Dừa đã đi vào văn học qua cuốn ký sự lịch sử của nhà văn Chu Lai.
Mỗi năm khu di tích đón hơn 10 nghìn lượt khách. Có những tù nhân cũ trở về thăm lại nhà ngục xưa. Nhiều du khách trẻ tuổi ở mọi miền đất nước, khi đến Phú Quốc du lịch, ngoài những thắng cảnh nổi tiếng, cũng không quên ghé thăm di tích này. Khách nước ngoài đến thăm di tích mỗi lúc một đông hơn. Còn học sinh trên đảo thường đến đây để học những trang sử sống động về Phú Quốc và lịch sử đấu tranh của dân tộc.
Tính đến tháng 10-2008, người ta đã tìm được tổng cộng 1.028 bộ hài cốt liệt sĩ tại nhà lao Cây Dừa. Hầu hết đều là liệt sỹ vô danh, không rõ họ tên, tuổi, quê quán, không rõ ngày hy sinh, do quá trình bị địch bắt giam, tù đày tra tấn đến chết ở đâu thì vùi xác tại đó. Theo một số tư liệu lịch sử, hiện nay, dưới lòng đất vùng nhà lao Cây Dừa còn có gần 3.000 bộ hài cốt liệt sĩ chưa được tìm thấy. Nơi được xác định nhiều hài cốt liệt sĩ nằm lại là ngọn đồi phía Tây Nam nhà lao. Tại đây, người ta đã cho xây dựng Khu Tưởng niệm hoành tráng, đồ sộ. Mới đây, Đội K92 Kiên Giang phát hiện thêm 268 bộ hài cốt liệt sĩ, nâng tổng số hài cốt liệt sĩ hy sinh tại Nhà tù Phú Quốc đã được tìm thấy lên 1.336 bộ.