1560s, from Latin clandestinus "secret, hidden," from clam "secretly," from adverbial derivative of base of celare "to hide" (see cell), perhaps on model of intestinus "internal." Related: Clandestinely. As a noun form, there is awkward clandestinity (clandestineness apparently being a dictionary word).
