1945년 10월 12일 『소련 제25군사령관 명령서』에 의하여 치안대, 자위대, 적위대를 모두 해산하고 보안대를 창설하였다. 보안대는 국내 치안을 위한 무장력으로서, 소련의 내무성 관할의 군대나 한국의 전투경찰과 유사한 성격의 부대로, 1950년 6월 한국전쟁 직전까지 약 5만 명으로 확장되었다.
소련군 제25군은 북한에 주둔하자마자 북한 내 자생적으로 창설된 군사단체를 해산하고 치안을 유지한다는 명분으로 보안대를 창설하였다. 이것은 소련군이 지방의 분권적 영향력을 통제하기 위하여 강력한 중앙 지도기관을 수립하기 위한 첫 조치였으며, 초기 북한의 치안용 무장 세력으로써 후에 정규 무장력의 기반을 구축하는 역할을 하였다.
소련 제25군사령관 치스챠코프 대장은 1945년 10월 12일 국내 각종 무장 세력의 해산을 지시하였다. 이 지시 직후 1945년 10월 21일 진남포(鎭南浦)에서 청년 2천여 명을 선발하여 보안대를 창설하였다. 1946년 초까지 설치된 6개 ‘도 보안대’는 주로 치안과 시설 경비를 담당하였으며, 신설된 각 분소에서는 각 지방 청년들을 입소시켜 보안대원과 철도경비원으로 육성하였다. 철도경비대(鐵道警備隊) 이후 북한지도부는 철도경비를 위한 추가적인 병력을 소련 군정 당국과 협의하여 각 도에 단위별로 철도보안대를 창설해 나갔다.
보안대 요원 선발은 주로 노동자, 빈농 등 일반인으로 구성하였으며, 이는 공산주의자 만으로 무장 세력을 조직하겠다는 소련 군정당국의 조치였다. 또 소련 군정당국은 그들이 신임할 수 있는 자들을 보안 기관에 배치하였고 이를 다시 소련계 한인 또는 소련 비밀경찰의 북한 지부를 통해 감시하였다.
각 도의 도 보안대가 창설되면서 이들에 대한 보충과 훈련을 위해 1946년 6월에는 ‘보안훈련소’를 개천에 설치하였다. 이어 신의주(新義州)에 ‘보안훈련소 제1분소’, 정주에 ‘보안훈련소 제2분소’, 강계(江界)에 ‘보안훈련소 제3분소’를 각각 설치하여 보안대원의 모집 · 훈련을 강화하였다.
보안대는 최초부터 정치적 성격을 강하게 띠고 등장하였으며 정권 장악을 위한 조직으로서 편성되었다. 그 결과 북한 주둔 소련군 사령부가 계획한 대로 김일성을 위시한 소위 ‘ 항일유격대’ 출신들이 전면에 나서게 되었고 또한 북한군과 더불어 군사력의 근간을 이루는 부대의 하나로 성장해 갔다.