勘解由使が設置された延暦16年（797年）頃から作成されたと考えられている。初出は延暦19年9月12日（800年10月3日）付太政官符（『延暦交替式』である。ただし、この時期の不与解由状は後任者が解由状を出さなかった理由について説明するために作成した文書（解）であったとみられている。
その後、大同2年4月6日（807年5月16日）付太政官符（『類聚三代格』巻12）にて不与解由状に後任者だけでなく前任者の署名も必要とされた。以後、不与解由状は従来の後任者が前任者の失政・財物の欠失などの問題点を指摘するだけでなく、それに対する前任者の説明・反論などの説明が併記されるようになった。また、従来単なる後任者の意見書に過ぎなかった不与解由状が勘解由使などの監査機関の審査の対象文書になり、前任者の責任追及に用いられるようになった。また、当初は国司の交替のみを対象にしていたが、交替手続の実施対象の拡大とともに大同4年（809年）には京官、貞観12年（870年）には諸寺の別当の交替の際にも作成が行われるようになった。延喜15年（915年）に受領功過定が開始されると、勘解由使の審査を経た不与解由状の内容や審査そのものに対する更なる審査が実施されるようになった。