1104년(숙종 9)에 동북면행영병마도통(東北面行營兵馬都統)으로서 여진정벌(女眞征伐)에 나섰다가 패하고 돌아온 윤관(尹瓘)은 기병의 수적 열세를 크게 느끼고 기병을 강화할 것을 건의하였다. 고려는 이 건의에 따라 여진족에 대항하기 위해 강력한 기병대의 편제를 갖춘 별무반(別武班)을 설치하였다. 그러나 보다 근본적인 설치 동기는 당시 이군 육위(二軍六衛)를 중심으로 하는 기존의 군사 체제가 붕괴되어 대규모의 군사 동원이 불가능한 현실을 극복하기 위한 조처였다. 별무반은 기병인 신기군(神騎軍), 보병인 신보군(神步軍), 승려들로 이루어진 항마군(降魔軍) 등으로 구성되었다.
조직은 기병과 보병으로 나뉘며, 문무(文武) 산관(散官)과 이서(吏胥)에서부터 장사꾼과 노복에 이르기까지 모든 백성을 징발 대상으로 하였다. 이들 가운데 말을 가진 자는 기병인 신기군(神騎軍)에 속했고, 말이 없는 자는 보병으로서 신보(神步) · 도탕(跳蕩) · 경궁(梗弓) · 정노(精弩) · 발화(發火) 등의 군에 편입시켰는데, 나이 스물 이상이면서도 과거 응시자가 아니면 모두 신보군에 속하게 하였다. 윤관의 건의에 따라 기병을 강화하기 위하여 별무반을 설치하기는 하였으나, 전마를 낼 수 있는 계층이 문무 산관 정도였으며, 마상 무예를 익히는 데에는 많은 시간이 걸렸기 때문에 기병은 생각만큼 강화되지 못하였다. 이를 보완하기 위하여 별무반 내에는 활(弓)과 노(弩)가 중심이 되는 특수 부대를 집중적으로 편성하였다. 별무반의 다수를 차지했던 신보군, 그 가운데서도 주 · 부 · 군 · 현 출신의 백성들은 주현군(州縣軍)으로서 일부 전투에 참가하기도 하였지만 대부분은 여진 지역을 점령한 뒤에 성을 쌓는 일 등 공역을 담당하였다. 그 밖에 승도(僧徒)들로 구성된 항마군(降魔軍)이 있었다.
이와 같이 여러 계층에서 동원된 별무반을 서반과 모든 진(鎭) · 부(府)의 군인과 함께 4계절 훈련시켜 대규모의 여진정벌을 계획하였다. 계획이 실천에 옮겨지기 전에 숙종(肅宗)이 승하했으나 그 뒤를 이은 예종(睿宗)이 적극적으로 여진정벌을 추진하였다. 특히, 예종은 즉위하자마자 곧 동계(東界)를 순시하게 하고 동계가발병마사(東界加發兵馬使) · 동계행영병마사(東界行營兵馬使) 등을 두어 동계 방면에 대한 군사 체제를 강화하였다.
그리고 1106년(예종 1) 7월 조정에서 동여진 정벌에 대한 의론이 있었다. 이때 도병마사(都兵馬使)는 앞서 동여진과의 싸움에서 패한 원인을 군령이 엄하지 못했기 때문이라 지적하면서, 일찍이 현종(顯宗) 때 거란 침입 시에 시행했던 군율을 따를 것을 청해 시행하게 하였다. 그해 윤관과 오연총(吳延寵)이 숭인문 밖에서 신기군과 신보군을 사열한 것으로 보아 별무반의 편성이 신속하게 추진되었음을 알 수 있다. 또한, 동여진 정벌의 주력 부대가 별무반이었음을 볼 때, 도병마사가 제청한 군령은 바로 별무반을 중심으로 한 군율이라 하겠다.
1107년(예종 2)에 윤관은 엄격한 군율 아래, 병기와 병술을 개량한 대병력의 별무반을 이끌고 여진족을 정벌하였다. 그리고 고려 동북쪽의 변경 지역을 개척하기 위해 구성(九城)을 쌓는 공적을 세웠다.
별무반은 여진정벌이 끝남으로써 해체된 것으로 보인다. 직업 군인이 아니라 임시적인 군사 조직이었음에도 불구하고, 전국적인 규모로 농민 중심 군사 부대가 조직되었다는 점은 고려의 군사 제도에 새로운 변화를 주었다는 측면에서 의의가 크다.