1904年
日俄战争时期，日本宪兵本部抽调、配属宪兵于满洲派遣军第三军兵站管理部。
1905年9月，沙皇俄国战败，日本得到南满铁路与辽东半岛，设置了“
关东总督府”和“南满铁道株式会社”。1905年12月，撤销辽东兵站监，将辽东兵站监的宪兵改编为“关东宪兵队”，福永定中佐任关东宪兵队队长，本部设在
旅顺口。下辖旅顺、奉天、安东、大连、辽阳、公主岭等宪兵分队。在鞍山、抚顺、本溪、四平、铁岭等地成立了宪兵分遣队。1906年10月，关东宪兵队被明文划归到
关东都督府隶下，任务是对驻满洲的日军师团及独立守备队执行军事警察和司法警察业务;在“
关东州”和
满铁附属地内兼负行政警察和司法警察责任。关东宪兵队的业务关系、人员培训等受日本国内宪兵司令部指导，称为“第十五宪兵队”。
1919年4月，日本把关东都督府一分为二：民政部改为“关东厅”，陆军部改为“关东军司令部”。7月，关东宪兵队划归日本宪兵司令部直属，专门对
关东军执行军事警察业务，将行政警察业务移交给关东厅。
“九一八”事变后，1931年9月21日，关东宪兵队升格为关东宪兵司令部，1932年6月脱离日本宪兵本部的隶属，转为关东军作战序列，受关东军司令官统辖。由“敕令宪兵”转为“军令宪兵”，按照“战地宪兵作战要务令”进行活动。关东宪兵司令部由旅顺迁至沈阳，现址为
东北育才学校初中部使用的北校区西楼。