Sejarah Kantor Imigrasi Kelas II TPI Sibolga diawali ketika diperlukannya kantor yang mengawasi daerah Tapanuli dan Nias. Yang dimulai dengan pendirian Pos Imigrasi Sibolga pada bulan Juli tahun 1969. Kemudian Pada tahun 1975 ditingkatkan menjadi Kantor Resort Imigrasi Sibolga dibawah Kantor Imigrasi Pematang Siantar. Setelah menempuh beberapa pengawasan dan telah terpenuhinya persyaratan menjadi sebuah kantor imigrasi yang berdiri sendiri Maka Kantor Resort Imigrasi Sibolga ditingkatkan menjadi Kantor Imigrasi Sibolga dengan klasifikasi sebagai Kantor Imigrasi Kelas II Sibolga. Hal ini dilakukan dengan mempertimbangkan potensi dan strategisnya wilayah Sibolga. Sehingga berdasarkan Surat Keputusan Menteri Kehakiman RI Nomor : M-02.PR.07.04 tanggal 10 Maret 1983 dan juncto Keputusan Menteri Kehakiman RI Nomor : M-04.PR.07.10 tanggal 29 Maret 1982 disahkanlah kantor imigrasi Sibolga dengan nama Kantor Imigrasi Kelas II SIBOLGA.