斎藤は、山口祐助とますの子として生まれ、父の山口祐助は播磨国明石藩の足軽であったとされているが、戊辰戦争後の斎藤の会津藩との関わりの深さから疑問視もされている。
斎藤は19歳の時に、江戸小石川関口で旗本と口論になり、相手を斬ってしまうと、父と兄に旅支度をさせられ、すぐに京都へと旅立った。
京都に着くと、父の友人が開いていた聖徳太子流剣術道場主に身をかくす。
一方、将軍・徳川家茂が京都に行った際の警護役として募集され浪士隊が江戸から京都にやって来ると、浪士隊は壬生浪士組に名を変え、同日、京都で新たに隊士を募集すると、斎藤を含めた11人が入隊し、京都守護職である会津藩(伝統的に幕府と縁が深い)の藩主である松平容保の預かりとなった。
斎藤と近藤や土方との接点には諸説あるが、この入隊時が出会いというのが有力視されている。
新選組幹部の選出にあたり、斎藤は20歳にして副長助勤に抜擢された。
後の組織再編成の際には三番隊組長となり、沖田や永倉らとともに新選組の撃剣師範を務める。
永倉は弟子に「沖田は猛者の剣、斎藤は無敵の剣」と語ったといわれ、剣の腕はあの沖田に匹敵する強さであった。
斎藤は、土方からの信頼が特に厚く、新撰組内部での粛清役や暗殺役といったダークな仕事を数多く務める。
また、その土方からの信頼の厚さゆえに、スパイとして組織外に派遣されることもあった。
斎藤が謎に包まれている部分が多い人物でもあるのは、記録に残せない影の仕事に関わる機会が多かったたである。
新撰組の名を天下に轟かせた池田屋事件の後、藤堂平助の仲介で才能豊かな伊東甲子太郎が新撰組に加わるが、近藤と伊東が時局を論じ合った際に、徳川幕府あっての尊王攘夷という考えを持つ近藤に対して、伊東は孝明天皇の衛士になることを主張したため、近藤は伊東らの分離を警戒した。
近藤の予想通り、伊東は新撰組から分離した御陵衛士を結成すると、斎藤は、土方の指示で、この伊東の御陵衛士に潜入スパイとして参加する。
新選組が伊東ら御陵衛士を暗殺した油小路事件は、斎藤がスパイとしてもたらした情報に基づいて計画・決行がなされた。
1867年11月9日に将軍・徳川慶喜は大政奉還を行い、朝廷から徳川幕府に貸し出されていた政治権力を明治天皇に返上し、1868年1月3日には岩倉具視らによって王政復古の号令が発して徳川慶喜の身分の剥奪と徳川家の領地全ての没収を決定し、明治新政府が樹立する。
こうして徳川幕府は政治の実権を完全に失うことになった。
どう好意的に解釈しようとしても暴虐で挑発的な薩摩藩に対して、徳川慶喜の周囲では「討薩」を望む声が高まり、慶喜は討薩を決定するが、1868年(明治元年)1月27日、旧幕府軍と新政府軍における「鳥羽・伏見の戦い」で旧幕府軍が敗れると、新選組も幕府軍艦で江戸へと戻る。
江戸に戻った新撰組は、旧幕府から新政府軍の甲府進軍を阻止する任務を与えられ、甲陽鎮撫隊と名を改めて、甲州街道から甲府城を目指して進軍するが、その途中、甲州勝沼の戦いにおいて新政府軍に敗退した。
斎藤はいずれの戦いでも最前線で戦うが、銃撃戦がメインの戦闘では大きな活躍を見せることが出来ずに終わる。
近藤が流山で新政府軍に投降して板橋刑場で斬首されたあと、斎藤は、土方歳三らと一旦別れ、隊士の一部を率いて会津へ向う。
斎藤ら新選組は、会津藩の指揮下に入り、白河口の戦いや母成峠の戦いにも参加するが、劣勢に次ぐ劣勢により若松城下に退却する。
この時、大鳥圭介らと共に宇都宮城の戦いに参加するも敗走してきた土方と再開した。
その後、土方は庄内から北へ北へと転戦し北海道まで行くが、斎藤は会津に残留し、会津藩士とともに城外で新政府軍への抵抗を続ける。
会津藩が新政府軍に降伏したあとも、斎藤は頑なに戦い続けるが、新撰組の雇い主であった松平容保の説得に応じて投降した。
新撰組時代の斎藤が、土方から厚い信頼をおかれていたのは、こうした強情で信念が固いながらもリーダーには従順な一面があったことによると推測が出来る。
捕虜となった斎藤は、旧会津藩領の塩川や越後高田で謹慎生活を送った。
謹慎生活を終えた斎藤は五戸に移住し、元会津藩では超がつく名家の篠田家のやそと結婚するが、この結婚生活は3年ほどで終わってしまう。
その原因については、不明であり、単に離縁だったのか死別だったのかも分かっていない。
斎藤にとって二度目の結婚の相手も元会津藩の大目付であった高木小十郎の娘である時尾であった。
この結婚には、元会津藩主・松平容保が上仲人、元会津藩家老の佐川官兵衛と山川浩、倉沢平治右衛門が下仲人を務める。
斎藤と時尾は三人の男の子に恵まれた。
こうした斎藤に対する元会津藩の扱いから、冒頭の出自の定説に疑問視の声が多くなっており、斎藤は実は歴とした会津藩出身の武士だったのではないかとも言われている。
明治7年(1874年)7月、東京に移住し、警視庁に採用され、内務省警視局で警部補に昇任し、西南戦争に参加した。
大砲2門を奪取するなどの大活躍をし、その様子は東京日日新聞に報道され、斎藤は政府から勲七等青色桐葉章と賞金100円を授与される。
その後、警視庁が再設置され、斎藤は麻布警察署詰外勤警部として勤務し、明治25年(1892年)に退職した。
警視庁退職時に、東京高等師範学校校長・高嶺秀夫(元会津藩士)らの推挙で、東京高等師範学校附属東京教育博物館(現在の国立科学博物館)の守衛長となる。
明治32年(1899年)には東京女子高等師範学校に庶務掛兼会計掛として勤務し、明治42年(1909年)に退職した。
そして、大正4年(1915年)9月28日、71歳で胃潰瘍のため東京府東京市本郷区真砂町で死去。永倉新八とほぼ同時期に死去したことになる。
新撰組ではスパイとして働く機会が多かったことから謎の多い人物であったが、長生きしたため、後年はいくらかの証言が残っており、刀での戦闘経験について「どうもこの真剣での斬り合いというものは、敵がこう斬りこんで来たら、それをこう払っておいて、そのすきにこう斬りこんで行くなどという事は出来るものではなく、夢中になって斬り合うのです。」という証言を残した。
日本史上最強という解釈もできる沖田総司に匹敵する強さであった斎藤の証言だけに、これが剣術のシンプルにして極意なのかもしれない。
また、子ども達には「武士たる者は、玄関を出るときは頭から先に出るな、足から出よ、不意に斬りつけられた場合、頭をやられれば致命傷だが、足ならば倒れながらも相手を下から突き上げて殺すことができる。」と説教するのを常としていた。
