Sinds de eerste minister van Justitie in 1815 werd benoemd, heeft het Ministerie van Justitie zich met vreemdelingenkwesties beziggehouden. In 1849 werd de eerste Vreemdelingenwet van kracht (Wet houdende toelating en uitzetting van vreemdelingen). Toen Nederland na de Eerste Wereldoorlog met een massale vluchtelingenstroom werd geconfronteerd, bleek er behoefte te zijn aan een wettelijke regeling voor het toezicht op vreemdelingen. De aanzet hiertoe werd gegeven door de Wet van 17 juni 1918 (Wet houdende nadere voorzieningen in de tegenwoordig buitengewone omstandigheden betreffende het toezicht op hier te lande vertoevende vreemdelingen) (Stb. 410), welke in het Koninklijk Besluit van 16 augustus 1918 (Stb. 521) werd uitgewerkt (gewijzigd bij KB van 13 oktober 1937 (Stb. 219)). Hoewel deze wet slechts voor de naoorlogse 'buitengewone omstandigheden' was bedoeld, zou hij in de praktijk tot 1965 van kracht blijven. Dit gold ook voor de wet van 1849 die formeel even lang van kracht bleef.

De Grensbewakingswet van 10 januari 1920 (Stb. 11) en het Bewakingsvoorschrift met de uitvoeringsvoorschriften van voornoemde wet (beschikking van de minister van Justitie van 21 februari 1920, 2e afd. A, nr. 858, Stcrt. van 26 april 1920 nr. 80, gewijzigd bij besluit van 27 augustus 1920, 2e afd. A nr. 904, Stcrt. van 6 september 1920, nr. 172, 1e bijvoegsel en bij beschikking van 25 mei 1938, 2e afd. A no 1190, Stcrt. no. 103) vormden samen met de wet van 1918 een instrument ten behoeve van de toelating en het verblijf van vreemdelingen en het vreemdelingentoezicht. De voornoemde wet werd door de wet van 29 juni 1925 (Stb. 308) gewijzigd. In verband met de toenemende oorlogsdreiging werd het Bewakingsvoorschrift van 1920 door dat van 1939 vervangen.

De inspecteur van de Koninklijke Marechaussee had de opperleiding van het vreemdelingentoezicht. Onder toezicht van de inspecteur leidde de administrateur van de Vreemdelingendienst de dienst.

De taak van het bureau was het houden van toezicht op vreemdelingen, het bijhouden van centrale registers van identiteitskaarten en controlepassen en de zorg dat door de hoofden van politie behoorlijk toezicht op de vreemdelingen werd uitgeoefend. Daarnaast nam de dienst beslissingen over aanwijzing van bepaalde verblijfplaatsen, ontzegging van verblijf en uitreiking van controlepassen en kennisgevingen (zie verder Grensbewaking). Een commissie van advies stond de inspecteur in zijn werk ter zijde.

Na overleg van de ministers van Buitenlandse Zaken, Justitie, Oorlog en Landbouw, Nijverheid en Handel werd met ingang van 15 november 1918 het Rijkspaspoortenkantoor ingesteld. Dit kantoor was namens de minister van Buitenlandse Zaken bevoegd diplomatieke en consulaire ambtenaren te machtigen om visa te verlenen. De leiding van het Rijkspaspoortenkantoor berustte bij de inspecteur van de Koninklijke Marechaussee. Formeel leidde ook hier de administrateur het kantoor namens hem.

Het kantoor hield zich in principe met twee zaken bezig: het beoordelen van alle visumaanvragen die vreemdelingen door tussenkomst van diplomatieke en consulaire ambtenaren hadden ingediend alsmede van verzoeken om verlenging van visa van reeds hier te lande verblijvende vreemdelingen. Het kantoor werd op 16 oktober 1926 opgeheven.

De uitvoering van het Bewakingsvoorschrift van 1920 lag bij de nieuw ingestelde Dienst Grensbewaking. Evenals bij de Vreemdelingendienst had de inspecteur van de Koninklijke Marechaussee ook hiervan de leiding. Formeel werd de dienst onder diens verantwoordelijkheid geleid door de administrateur van de Grensbewaking. De werkzaamheden bestonden overeenkomstig bepalingen van het Bewakingsvoorschrift uit het regelen van de toegang tot het verkeer binnen en het verlaten van de bewakingsgebieden. Omstreeks 1927 werd de naam gewijzigd in Grensbewaking en Vreemdelingendienst. Vanaf 1930 werd dit Vreemdelingendienst en Grensbewaking. Evenals toen de beide diensten nog naast elkaar fungeerden, bleef de namens de inspecteur van de Koninklijke Marechaussee gevoerde leiding hierna bij één administrateur liggen.

In 1939 kwam er een Rijksvreemdelingendienst die rechtstreeks onder de minister van Justitie viel, aanvankelijk als onderdeel van de (Rijks)recherchecentrale (Vijfde afdeling van het departement van Justitie). (De naam Rijksvreemdelingendienst komt vanaf 1937 voor in de stukken). Deze dienst werd belast met de doorlating van vreemdelingen en de verblijfsontzeggingen uit de bewakingsgebieden, de centrale registratie van hier te lande verblijvende en van ongewenste vreemdelingen en het machtigen van consulaire ambtenaren in het buitenland tot het verlenen van visa. Nadat deze dienst tijdens de Tweede Wereldoorlog een slapend bestaan had gekend, kwam deze dienst onder de Directie Politie van het Ministerie van Justitie te vallen en heette het tot circa 1955 Bureau Rijksvreemdelingendienst. Daarna verviel de toevoeging Bureau.

Op 1 mei 1956 werd de Rijksvreemdelingendienst opgeheven. Deze werd opgevolgd door de Hoofdafdeling Vreemdelingenzaken en Grensbewaking (tot 1976), de Directie Vreemdelingenzaken (1976-1994) en de Immigratie- en Naturalisatiedienst (1994-...).

Bij de opzet van de administratie van de voormalige Rijksvreemdelingendienst is men uitgegaan van het standpunt dat een binnenkomende of uitgaande brief moest worden geagendeerd naar de inhoud van de brief. Vroeg een persoon bijvoorbeeld tijdelijk verblijf aan, dan kreeg de brief nummer tv-1 (tijdelijk verblijf, volgnummer 1), vroeg dezelfde persoon later een visum aan, dan kwam het stuk onder m of mv (machtiging visum) in een nieuw dossier terecht. Er konden zo dus over één persoon meerdere dossiers worden aangelegd. Vanaf 1948 of 1949 is men overgaan op één dossier per persoon. Daarna werden zogenaamde stockletterloze dossiers aangelegd.

Overbrenging van een overheidsarchief