اصطلاح عربی برای موزاییک «فسیفساء» است. این اصطلاح، رونویسی عربی از واژه یونانی بیزانسی Ψηφιδωτό است و هنر موزاییک در امپراتوری بیزانس به شکوفایی چشمگیری رسید. موزاییک‌های به سبک بیزانسی، کلیساها، کنیسه‌ها و معابد ایالت Provincia Palaestina (Prima، Secunda و Tertia) را زینت می‌داد؛ این ایالت‌ها از قرن چهارم به بعد با موزاییک‌های دیواری، سقفی و کفی به‌طرز ظریفی آراسته می‌شدند. هم کلیسای نوا (Νέα Ἐκκλησία) در ایلیا کاپیتولینا (بیت‌المقدس)، که یوستینیانوس یکم (۵۲۷–۵۶۵) آن را برپا کرد، و هم کلیسای مولد عیسی در بیت‌لحم، که به‌عنوان یک باسیلیکای بزرگ دوران کنستانتین ساخته شده بود، با موزاییک تزئین شده بودند. کف موزاییکی اصلی کلیسای مولد عیسی، با نقوش هندسی رومی‌اش، امروز تا حدی باقی مانده است. همان‌طور که پیش‌تر نشان دادیم، خود نام این سرزمین، Palaestina، به یونانی (Παλαιστινη)، بر نقشه معروف موزاییک مادبا، مربوط به سال‌های ۵۶۰ تا ۵۶۵ میلادی، در شهری یافت شد که در آن زمان بخشی از استان بیزانسی Palaestina Prima بود. موزاییک‌های عربی مشابه به سبک بیزانسی در کاخ هشام اموی (قصر هشام) در خربة المفجر، یک محوطه باستان‌شناسی مهم اسلامی متعلق به صدر اسلام که ۵ کیلومتری شمال شهر اریحا واقع است، کشف شدند. بسیاری از یافته‌های کاوش‌های این محوطه اکنون در موزه راکفلر (که پیش‌تر موزه باستان‌شناسی فلسطین نام داشت) در بیت‌المقدس شرقی اشغال‌شده نگهداری می‌شود.