วัดเขาบันไดอิฐเชื่อกันว่าเป็นศาสนสถานตั้งแต่สมัยสุโขทัยเป็นราชธานี แต่หลักฐานในทางโบราณคดีที่หลงเหลืออยู่เป็นยุคช่วงกลางของกรุงศรีอยุธยา ราว พ.ศ. 2171 ในสมัยสมเด็จพระเชษฐาธิราชได้จับพระศรีศิลป์ (เชื้อสายพระเจ้าทรงธรรม) เนรเทศมาคุมขังในถ้ำภายใต้เขาบันไดอิฐแห่งนี้ ก่อนที่จะนำกลับไปสำเร็จโทษที่อยุธยา

ส่วนอีกตำนานระบุว่า ราว พ.ศ. 2240 ที่นี่เป็นที่ที่พระอาจารย์แสงผู้ชำนาญเรื่องเวทย์มนต์คาถาและเป็นอาจารย์ของพระเจ้าเสือ เคยอาศัยเป็นที่นั่งวิปัสสนา และพระเจ้าเสือเคยมาที่นี่ประจำก่อนออกศึกทุกครั้ง พระอาจารย์แสงอยู่จนกระทั่งมรณภาพ จึงถือว่า พระอาจารย์แสงเป็นเจ้าอาวาสรูปแรกของวัดเขาบันไดอิฐ อย่างไรก็ตาม เมื่อพระอาจารย์แสงมาจำพรรษาที่นี่ พระเจ้าเสือก็เสด็จมาเยือนหลายครั้ง และนิมนต์กลับกรุงศรีอยุธยาแต่ไม่สำเร็จ จึงได้บูรณปฏิสังขรณ์วัดเขาบันไดอิฐ สร้างพระพุทธรูปปางประทับยืนไว้ในถ้ำ (ชาวบ้านเรียกพระพุทธเจ้าเสือ) และได้พระราชทานเรือแก่พระอาจารย์เพื่อใช้ในการสัญจรไปมา (ปัจจุบันประทุนเรือยังเก็บไว้ภายในถ้ำพระเจ้าเสือ)[1]

เมื่อครั้งสุนทรภู่เดินทางมาเพชรบุรี ระหว่าง พ.ศ. 2388–2392 ได้ประพันธ์นิราศเมืองเพชร ได้พรรณาถึงวัดเขาบันไดอิฐ