조선 전기에 두만강유역의 영토확장에 따라 육진(六鎭)을 설치하고, 성벽으로 둘러싸인 요새지를 구축한 다음, 1440년(세종 22)에 행성의 축조가 계획되었다. 평안도의 압록강유역 행성과 함께 계획되어 10년 동안에 모두 67만2134척(尺)의 행성이 축조되었다.
성벽은 지형에 따라 축조방법을 달리하였는데, 산비탈과 능선은 삭토(削土) 방법으로 하고, 평탄한 지형은 돌로 내외협축(內外夾築)하였으며, 지대가 낮고 습기가 많은 곳은 녹각(鹿角 : 가지가 있는 나무를 비껴 꽂은 성벽)과 목익(木杙 : 나무말뚝)으로 하였다.
세종 때에 쌓은 곳은 온성군의 동쪽 입암(立巖)에서 시작하여 두만강을 거슬러 올라가 종성군을 지나고, 회령읍성(會寧邑城)의 앞쪽 들판까지 200리(里)나 되었으며, 갑산군의 지항포동구(池巷浦洞口)의 동쪽 봉우리에서 옛 군영터에 이르는 1리 249보(步), 그리고 삼수군의 어면강동구(魚面江洞口)에서 상목평(桑木坪)까지 29리 239보였다.
그 뒤 문종 때와 중종 때에 이르러 세종 때 쌓은 나머지 구간에 대한 일부의 연장된 행성이 축조되기도 하여, 여진족과의 문화적·군사적 경계선 구실을 하였다.