1830年9月26日、薩摩国鹿児島城下高麗町（現：鹿児島県鹿児島市高麗町）に下級藩士の長男として生まれる。

幼少期に加治屋町に移住し、下加治屋町の郷中（薩摩藩の武士階級子弟の教育法）や藩校で西郷隆盛らと共に学問を学び、親友・同志となる。

大久保利通は胃が弱く、武術は得意ではなかったが、討論や読書などの学問では抜きん出ていた。

1850年、20歳のとき、お由羅騒動で父とともに連座して罷免され謹慎処分となり、大久保家は貧しい生活を強いられた。

島津斉彬（1809～1858）が藩主になると大久保は謹慎を解かれ、1853年に記録所に復職し、御蔵役となる。

1857年、27歳の大久保は西郷隆盛とともに薩摩藩の徒目付となり、また藩内組織・精忠組の長として活動。

1858年に薩摩藩主の島津斉彬が急逝すると、斉彬の手足となって活動していた西郷隆盛も失脚。代わりに大久保利通が新藩主の実父・島津久光に接近し、側近となる。

1866年、36歳の大久保は江戸幕府の第二次長州征討に反対。薩摩藩の出兵拒否を行なう。翌年、西郷隆盛らと雄藩会議を計画し、四侯会議を開催するも第15代将軍・徳川慶喜によって頓挫。以降、武力倒幕路線を指向する。

その後、倒幕実行の直前まで持ち込むが、1867年11月に徳川慶喜が大政奉還を建白した。

1868年、鳥羽・伏見にて旧幕府軍と薩摩藩との間で戦端が開かれ、戊辰戦争へと拡大。西郷隆盛と勝海舟との会談後、江戸城の無血開城が行なわれる。

明治維新後の1869年、38歳の大久保利通は参議に就任。版籍奉還、廃藩置県など、中央集権体制の確立を行う。

1871年に岩倉使節団の副使として外遊。帰国後、朝鮮出兵を巡る征韓論論争で西郷隆盛や板垣退助らの征韓派と対立、西郷隆盛らを失脚させる。

1873年、43歳の大久保は内務省を設置。初代内務卿として実権を握ると学制や地租改正、徴兵令などを実施。富国強兵をスローガンとして国家の近代化を推進した。

1877年、鹿児島の私学校生徒の暴動に端を発し、西郷隆盛を指導者とする西南戦争が起こる。大久保利通は京都から政府軍を指揮。西郷隆盛は敗れて、城山にて自刃。

西南戦争の翌年、1878年5月14日、大久保利通は石川県士族により紀尾井坂にて暗殺され、47年の生涯を閉じた。

大久保利通は、西南戦争前に西郷の参加を知り、西郷と会談したいと鹿児島への派遣を希望。しかし、殺害を危惧した伊藤博文らに朝議で反対される。西郷死亡の報せを聞くと大久保は号泣し、時々鴨居に頭をぶつけながらも家の中をグルグル歩き回っていたという。大久保の暗殺時には、生前の西郷からの手紙を持っていたとされる。