奈良時代に編纂された万葉集には、「戯書」と呼ばれる万葉仮名を使った強引な当て字による言語表現があり、なぞなぞに通じる遊び心を酌み取ることができる。
平安時代にはなぞなぞは「なぞなぞ物語」と呼ばれており、貴族のあいだでは歌合から派生した「なぞなぞ合(あわせ)」が行われた。なぞなぞ合は左右に分かれて互いに和歌の知識を婉曲に問うもので、返答も答えを含めた和歌を詠むことで行われた。鎌倉時代に入るとなぞなぞ物語は「なぞなぞ」「なぞたて」と呼ばれるようになり、質問は和歌より盛んになった連歌の技法である賦物の影響を受けるようになった。中御門宣胤の日記『宣胤卿記』には当時のなぞなぞが収録され、宣胤が謎連歌を自作した記事が残されている。
室町時代には宮中以外でも、文芸好きの僧侶や侍によってなぞなぞが楽しまれるようになり、後柏原天皇・後奈良天皇真筆と言われる宸翰本『なぞたて』など、なぞなぞ集が作られるようになった。しかし、江戸時代に入るとなぞなぞは大衆化・演芸化し、連歌の流れをくむなぞなぞは埋没してしまった。
江戸時代より伝承されているなぞなぞには、「なーんだ」「なんでしょう」などで問いかける二段謎と、今日でも寄席芸のひとつである都々逸や大喜利のなぞかけとして創作されている「○○とかけて、△△と解く、その心は」という三段謎がある。問い・答え・答えの解説から成る三段謎は、江戸時代初期の歌舞伎踊りの歌詞に見られるように演芸・話芸などの興業や、なぞなぞ本として盛んに出版された。
現代の日本では、最後の「何だ」という文句を「なーーんだ」と節をつけて歌うように語る事が多い。
なお、なぞなぞの一種である「絵解きなぞなぞ」の起源は、平安時代から江戸時代初期にかけて完成された「判じ物」（はんじもの）（※判じ絵、語り絵、絵考（絵考え）などとも呼ばれる）にある。
スフィンクスのなぞなぞ（ギリシャ神話より）.