"Nghìn lẻ một đêm" được tạo nên qua một quá trình kéo dài nhiều thế kỷ. Tác phẩm hoàn chỉnh vào thế kỷ 15 nhưng những phần cốt yếu như truyện nền, các truyện kể chính đã hình thành trong khoảng thời gian từ trước thế kỷ 9 cho đến thế kỷ 12. Dấu vết của Nghìn lẻ một đêm được tìm thấy trong văn bản viết sớm nhất vào khoảng thế kỷ thứ 9 trong một cuốn papyrus. Ngay trong cuốn papyrus này đã có sự đề cập đến tựa đề Sách về các câu chuyện từ Một nghìn đêm và tên của hai nhân vật là nữ Dinazad và Shirazad - sau này trở thành Dunyazad và Shahrazad. Khoảng một thế kỷ sau đó, một tác giả ở Baghdad, sử gia al-Mas‘ûdî (896-956) cũng nói về tác phẩm gồm các câu chuyện được kể trong các đêm với các nhân vật trong truyện nền là hoàng đế, quan tể tướng, con gái tể tướng và cô nữ tỳ trong sách Bãi vàng (Murûj adh-dhahab) của mình.