De nadruk van de missie lag op het opsporen van krijgsgevangenen en geheime agenten. Daarnaast maakte het hoofdbestuur van de PTT gebruik van de bepaling in de instellingsbeschikking dat ook 'daarvoor in aanmerking komende personen' opgespoord konden worden.
Met het traceren van vermisten werd begonnen in Nederland door informatievergaring bij onder andere degene die een opsporingsaanvraag had ingediend. Pas als het onderzoek in Nederland geen resultaten opleverde, werd met een onderzoeksteam in het buitenland verder gezocht.
De opsporingswerkzaamheden werden gecoördineerd door het registratiebureau van de missie, waar ook alle gegevens werden verzameld, uitgewerkt en in kaart gebracht. Verder verwerkte het registratiebureau de wekelijkse rapporten van alle officieren en onderhield het contact met instanties als het ministerie van Oorlog, het ministerie van Sociale Zaken, het Informatiebureau van het Nederlandse Rode Kruis en de verschillende missies. Daarnaast was het de taak van het bureau om de betrokken families op de hoogte te houden van de stand van zaken.
Naar schatting zijn ongeveer 200 militairen en 100 PTT werknemers getraceerd.
De Missie tot Opsporing van vermiste Nederlandse Militairen en Agenten werd, na centralisatie van het opsporingswerk bij het ministerie van Sociale Zaken, opgenomen in de nieuw opgerichte Nederlandse Missie tot Opsporing van Nederlandse Personen uit de Bezettingstijd. De werkwijze van deze organisatie was voor een groot deel geënt op de Missie tot Opsporing van vermiste Nederlandse Militairen en Agenten.