Menurut Reggie Baay di dalam bukunya Nyai dan Pergundikan di Hindia Belanda (2010), istilah nyai berasal dari bahasa Bali. Istilah itu dikenal ketika budak-budak perempuan dari Bali datang ke Batavia, pada abad ke-17, saat Vereenigde Oostindische Compagnie (VOC) atau Kongsi Dagang Hindia Timur berkuasa. Mereka pun dikenal dengan istilah gundik.
Istilah dalam bahasa Belanda untuk seorang gundik, menurut Tineke Hellwig di dalam bukunya Citra Kaum Perempuan di Hindia Belanda (2007) ialah hushoudster, bijzit, menagere, dan meid. Di tanah Melayu, gundik dikenal dengan sebutan munci.
Nyai pun kerap disebut meubel (perabot) atau inventarisstuk (barang inventaris), yang bisa dilelang maupun dikembalikan ke asalnya. Di sisi lain, nyai juga dianalogikan sebagai “boek” (buku) dan “woordenboek” (kamus), yang merujuk pada fungsi mereka sebagai penerjemah dan pengajar bahasa pribumi.
Di dalam surat kabar De Waarheid edisi 30 Oktober 1986, Anneke Teunissen menulis, kehadiran VOC berangsur-angsur mengukuhkan praktik pergundikan dalam kehidupan masyarakat Eropa di Hindia Belanda. Pria-pria Eropa butuh pelampiasan seksual di tanah yang jauh dari negaranya. Di dalam praktiknya, nyai bukan sekadar teman tidur, melainkan pula pengurus rumah tangga.