Als begin van de verzameling geldt traditioneel het jaar 1839, toen een aantal boeken van de Raad voor de Koophandel en Koloniën bij elkaar werd gebracht in een kamer op het Ministerie van Marine en Koloniën op het Binnenhof te Den Haag. Een aantal van deze boeken was mogelijk ook afkomstig van het toenmalige Departement van Publieke Onderwijs, Nationale Nijverheid en Koloniën. Tegen het midden van de negentiende eeuw werd ‘Koloniën’ een zelfstandig departement en de bibliotheek groeide langzaam in omvang. De bibliotheek werd voornamelijk gebruikt door ambtenaren, maar ook steeds meer door studenten. Tijdens de Tweede Wereldoorlog liet de bezetter de bibliotheek, die bijna 100.000 delen omvatte, vertrekken van het Binnenhof, en de verzameling werd verplaatst naar de zolder van het Vredespaleis te Den Haag. Na de bevrijding keerde de bibliotheek weer terug naar de oude plek. In de jaren hierop werd de naam en status van de bibliotheek verscheidene keren aangepast. Eerst werd ‘Koloniën’ vervangen door ‘Overzeese Gebiedsdelen’, en dit werd hierna ‘Zaken Overzee’. Uiteindelijk zou de bibliotheek een onderdeel worden van het Ministerie van Binnenlandse Zaken. Na de overdracht van de soevereiniteit over Nieuw-Guinea in 1962 besloot de regering tot een herschikking van de nu alleen nog op de koninkrijksdelen in de ‘West’ gerichte departementstakken. De bibliotheek van ‘Koloniën’ en het er omheen gegroeide documentatieapparaat zijn daarbij opgeheven.

In 1858 verscheen een eerste gedrukte catalogus van de bibliotheek. De lijst bevat beknopte beschrijvingen van zo’n 2.000 titels, merendeels uitgaven uit de 19e eeuw. De catalogus vermeldt ook een aantal drukken van voor 1800. Een tweede gedrukte catalogus verscheen in 1884 en vijftien jaar later waren omvang en gebruik van de bibliotheek al zo toegenomen dat alweer een nieuwe catalogus nodig bleek. Deze verscheen in 1898 en telde bijna 1000 bladzijden. Deze ‘Catalogus van de boeken en kaarten uitmakende de Bibliotheek van het Departement van Koloniën’ zou door geregeld verschijnende supplementen uiteindelijk een omvang van 11 delen krijgen. Het laatste supplement verscheen in 1930.