兵庫県西宮市の生まれ。市立西宮東高校を卒業後、千葉真一主宰の“ジャパンアクションクラブ（JAC）”に入り、真田広之の付き人をつとめる。1984年、千葉演出の『ゆかいな海賊大冒険』で初舞台。翌年には坂東玉三郎主演の『天守物語』などの舞台やNHKのドラマ『オアシスを求めて』に出演し、真田主演の井筒和幸監督「犬死にせしもの」86でチンピラ役を演じて、映画デビューを果たす。その後、JACを退団し、森田芳光総指揮のオムニバス「バカヤロー！２・幸せになりたい。」89の第２話「こわいお客様がイヤだ」にもコンビニ店員役で出演したが、初期の活動はあくまで舞台が中心で、デヴィッド・ルヴォー演出『双頭の鷲』90・94、『テレーズ・ラカン』93・98、『マクベス』96に連続出演したのをはじめ、野田秀樹演出『真夏の世の夢』92、『キル』94・97、アラン・アッカーマン演出『娘に祈りを』98、『橋からの眺め』99など、大物演出家に次々と起用されて演技力を磨いていった。97年、紀伊國屋演劇賞個人賞を受賞。舞台と並行して、テレビドラマにも比較的早くから顔を出し、87年のNHK大河ドラマ『独眼竜政宗』に蘆名義広役で出演。その後も『武田信玄』88、『翔ぶが如く』90、『八代将軍吉宗』95、『元禄繚乱』99と大河ドラマにはたびたび出演しているが、堤の名を世に知らしめたのは、民放連続ドラマの初レギュラーで、いきなり準主役に起用された96年のフジテレビ『ピュア』だった。ここで、和久井映見演じる知的障害者のヒロインと交流を深めていくフリー記者の沢渡徹役を好演。一躍、全国区の人気を獲得する。99年のTBS『ザ・ドクター』で患者思いの心優しい医師・麻生一真役を演じて、連ドラ初主演。続く2000年のフジテレビ『やまとなでしこ』では、松嶋菜々子演じる拝金主義のヒロイン・桜子と合コンで知り合い、医者だと偽って付き合うことになってしまう魚屋の男性・欧介を、誠実な等身大のキャラクターとして造形し、絶大な支持を得た。その後も、フジテレビ『恋ノチカラ』02、『ビギナー』03、『恋におちたら・僕の成功の秘密』05、NHK大河ドラマ『武蔵／MUSASHI』03、TBS『GOOD LUCK!!』03、『セーラー服と機関銃』06など多数のドラマに出演を重ねる。その間、映画では96年のSABU監督のデビュー作「弾丸ランナー」に主演し、銀行強盗未遂犯の田口トモロヲ、薬物依存症のコンビニ店員のダイアモンド☆ユカイとともに、ひょんなことから追いかけっこを展開するやくざの武田をアクティブに演じる。SABUの監督作品では、以後も「ポストマン・ブルース」97、「アンラッキー・モンキー」98、「MONDAY」00、「DRIVE」02と連続して主演をつとめ、いずれもトラブルに巻き込まれたり窮地に陥ったりする不運な男の悲喜劇を描き、実直さ、生真面目さが笑いを誘うという堤の逆説的な演技が光る。05年には、直木賞作家の金城一紀が原作・脚本をつとめ、岡田准一が主演した成島出監督「フライ,ダディ,フライ」05に助演。娘に暴力をふるった高校生ボクサーに復讐するため、在日高校生の主人公からケンカの特訓を受ける平凡なサラリーマンの鈴木役で、JAC仕込みのアクションも披露した。昭和30年代の東京を舞台にした山崎貴監督「ALWAYS／三丁目の夕日」05では、心温かく威勢のいい下町の自動車工場社長を熱演して日本アカデミー賞の最優秀助演男優賞を受賞。また、「フライ,ダディ,フライ」と併せて、キネマ旬報賞、ブルーリボン賞、報知映画賞など、この年の助演男優賞を総なめにする。大ヒットを受けて、07年に続編「ALWAYS／続・三丁目の夕日」も作られたこの作品で、名実ともに日本映画界の名優の位置に仲間入りを果たしたと言える。以後も、篠原哲雄監督「地下鉄（メトロ）に乗って」06、水田伸生監督「舞妓Haaaan!!!」07などを経て、08年に出演した原田眞人監督「クライマーズ・ハイ」、西谷弘監督「容疑者Ｘの献身」の２作で報知映画賞の主演男優賞を受賞。脳死肝移植というタブーに挑む医師を重厚に演じた成島監督「孤高のメス」10では、毎日映画コンクールの男優主演賞に輝いた。金城一紀脚本、岡田准一主演と「フライ,ダディ,フライ」のトリオが再結集したフジテレビのドラマ『SP／警視庁警備部警護課第四係』07ではさらに深化したアクションが展開され、堤は岡田演じる主人公のSP（警備警察官）の上司である尾形総一郎役に扮し、完結編となる映画版「SP／野望篇」10、「SP／革命篇」11の２作でも続けて同じ役を演じ、大ヒットに貢献した。また、自身にとっても「原点」だと語る舞台にも、いのうえひでのり演出『野獣郎見参』01、『吉原御免状』05、蜷川幸雄演出『欲望という名の電車』02、『タンゴ・冬の終わりに』06、ケラリーノ・サンドロヴィッチ演出『労働者Ｍ』06、千葉哲也演出「アット・ホーム・アット・ザ・ズー」10などに、毎年のように出演を重ねている。12年公開予定のシリーズ第３作「ALWAYS／三丁目の夕日'64」、森義隆監督「宇宙兄弟」の２作が待機中。