De aanleiding voor de oprichting van de Commissie van Advies en Overleg was de behoefte tot reorganisatie van alle opsporingswerkzaamheden. Er was tot op dat moment geen centrale leiding die deze werkzaamheden coördineerde en daardoor vielen bepaalde gebieden in Europa buiten de opsporingsactiviteiten. Ook was er weinig samenwerking tussen de verschillende instanties en was de invloed van de overheid op de werkzaamheden gering. Dit had tot gevolg dat de resultaten van het opsporingswerk niet bevredigend waren.
Hoofdbestuurslid van de Nederlandse Vereniging van Ex-Politieke Gevangenen, Kolonel W.Ch.J.M. van Lanschot, had een plan ontwikkeld voor de reorganisatie van de opsporing van vermisten, dat onder andere voorzag in de oprichting van een Commissie voor Advies en Overleg. Daarnaast werd er een Missie tot Opsporing van Vermiste Personen uit de Bezettingstijd ingesteld die verantwoordelijk zou worden voor de daadwerkelijke opsporing van vermisten in het buitenland. Voorts zou het Informatiebureau van het Nederlandse Rode Kruis (Nationaal Opsporingsbureau) belast worden met de administratieve en voorbereidende werkzaamheden van het opsporingswerk.