テンコジ
結成以前
この二人は天山（当時は本名の山本広吉）が1990年新日本プロレス入門で小島が翌1991年入門のほぼ同期の間柄であり、小島のデビュー戦の相手は山本が務めている。ヤングライオン時代からよく前座の試合でタッグを組んでおり、金本浩二&西村修とのタッグマッチでは前座の試合ながら週刊プロレスの巻頭カラー3ページを飾ったこともある。
結成
1993年のヤングライオン杯優勝後山本は海外武者修行に出発し、1995年に「天山広吉」とリングネームを改め凱旋。蝶野正洋・ヒロ斎藤と狼群団を結成するなど活躍する。その後狼群団はnWoジャパンへと発展し新メンバーとして武藤敬司が加入。武藤は蝶野のケガによる欠場中に当時新日本体所属だった小島をnWoジャパンに勧誘し小島もこれに同意し軍団入りする。しかし天山ら旧来からのメンバーはこれに反発し両者の間には軋轢が生じるが1998年のSGタッグリーグ公式戦の武藤&小島vs天山&nWoスティングの試合で戦いを通じて小島のことを理解し軍団入りを認める。そして翌1999年1月4日天山と小島はヤングライオン時代以来のタッグで天龍源一郎&越中詩郎組の保持するIWGPタッグ王座に挑戦しこれを奪取する。以後このベルトを巡り永田裕志&中西学組と抗争を展開し新日本のタッグ戦線を盛り上げる。2000年にはその活躍が認められプロレス大賞の最優秀タッグチーム賞を獲得した。
しかし2002年に小島は武藤と共に全日本プロレスに移籍が決定する。そして新日本プロレス所属の最後の試合はやはりテンコジで、試合後花道を去ろうとする小島にマイクを握った天山は「小島、出て行け、タコ! 全日本でも…どこだろうと！頑張れよお前！わかってんのか！コジ！わかったか！」と天山一流のエールを送り、小島はこれに深々と頭を下げ花道を去り天コジは解散となった。
再結成
2005年、天山はIWGPヘビー級チャンピオンとして、小島は三冠ヘビー級チャンピオンとして史上初の四冠統一戦のリングで向かい合った。試合は59分45秒で天山が脱水症状を起こしKO負け、小島が初の四冠王に輝いた（その後IWGP王座はリターンマッチが行われ天山が王座奪回）。2006年にはG1 CLIMAXに小島が出場。大会前に「眼中に無い」と言われ発奮した天山と決勝を戦い天山が優勝。この決勝での激闘を通じて二人は互いに歩み寄るようになりその年の世界最強タッグ決定リーグ戦にテンコジとして出場し見事優勝を果たした。
それからしばらくは目立った活動は無かったが、2008年7月8日に天山が抗争を繰り広げていた飯塚高史とのランバージャック・デスマッチに勝利後G・B・Hに袋叩きにされている所に全日本を負傷欠場中だった小島が救出に駆けつけ「真壁&G・B・H、よく聞け。俺たちが世界で一番有名で、世界で一番かっこいいタッグチーム、天山&小島、略してテンコジだ、バカ野郎!」とマイクアピールし、再びテンコジとして活動していくことをアピールする。それから数試合新日本と全日本のビッグマッチで勝利を積み重ねた二人はプロレス界イチ泣かせるタッグチームというやたらと長いチーム名で満を持してG1タッグリーグに出場。初戦こそ落としたもののそれ以降順調に勝ち続け決勝トーナメントも制して優勝。そして世界最強タッグ決定リーグ戦でも負傷に苦しみながらも優勝を遂げた。
2009年1月4日の東京ドーム大会では真壁刀義&矢野通組のIWGPタッグ王座にチーム3Dと共に3WAY戦で挑戦することが決まっていたが天山が網膜剥離で欠場を余儀なくされた。
天山はそれから4か月後の5月3日に復帰。復帰戦でチーム3Dに移っていたIWGPタッグの挑戦権を巡り、ジャイアント・バーナード&カール・アンダーソン組と対戦したが、天山がアンダーソンに敗北。試合後「いつまでもコジに迷惑掛けられへん」と活動休止を宣言した。
2010年に入り天山は長期休養から復帰、小島はフリーとして「小島軍（仮）」として新日本に上がると敵対をしていたが、鈴木みのるが小島軍を乗っ取り追い出されると試合は直接は無かったがフェードアウトする形となる。
再々結成
2011年8月、G1 CLIMAXで天山と小島が同じブロックにエントリーし、6年振りに対決。結果は天山がオリジナルTTDで小島からピンフォール勝ち。さらにこの試合で小島は右目眼窩底骨折と診断され欠場。後日開催されたALL TOGETHERでは久しぶりに同じコーナーに立つことが注目されていたが、実現不可能に終わる。
9月19日、欠場中の小島がリングに上がり、新日本プロレス社長菅林直樹の口から同団体への再入団を発表。復帰戦の相手として天山を指名する。
10月10日両国大会にて公約通りに対戦が組まれ、小島がラリアットで勝利を飾る。11月12日大阪大会で決着戦が行われ、天山がムーンサルトプレスで勝利を収める。試合後に因縁の相手である飯塚高史から襲撃を受けスリーパーホールドを極められるも、一旦花道に引き上げた小島がリングに戻り飯塚を追い払った。両者共に握手は交わさなかったものの、これを機に次期シリーズではCHAOSのメンバーからリンチを受けた際に救出に駆け付ける場面が頻繁に見られた。そして11月27日、小島のテンコジ復活の呼びかけに天山が応じ、晴れて再々結成となった。12月4日愛知大会で飯塚、ヒデオ・サイトー組と対戦。ブランクを感じさせないタッグワークをこなし、最後は天山が飯塚からアナコンダバイスでタップを奪い勝利した。
2012年1月4日、BAD INTENTIONS（ジャイアント・バーナード、カール・アンダーソン組）の保持するIWGPタッグ王座に挑戦。天山がムーンサルトプレスでバーナードを葬り去り、第58代IWGPタッグ王者に戴冠。2月12日にリターンマッチを要求してきた同タッグチームに初防衛戦を行い、小島がバーナードをラリアットで勝利を収めた。
3月18日には高山善廣、ランス・アーチャー組を退け2度目の防衛に成功するも、試合終了後に乱入してきた矢野通、飯塚にタッグ王座を強奪される。4月8日に一時は取り戻すことに成功するも、休憩中のサイン会に襲撃をかけられ再度強奪された。
5月3日福岡大会、矢野、飯塚組と正式なタイトル戦が組まれ対決。試合終盤に天コジが持ち込んだ手錠を逆に利用され、小島が孤立。さらにレフェリー不在の中でラフ殺法を展開させ、最後は小島が矢野の鬼殺しでピンフォール負けを喫し王座陥落となった。試合後のコメントブースで納得のいかない天山と小島は再戦を訴え、6月16日に同カードが組まれるも、試合の収拾がつかなくなりノーコンテスト裁定が下る。
7月22日山形大会、王座を剥奪されて尚もベルトを持参する矢野、飯塚組と三度対戦。レフェリーが4人という厳重態勢で行われた試合を制し、タッグ王座に返り咲くことに成功した。
10月8日両国国技館大会、鈴木軍のK.E.S.を相手に迎えたIWGPタッグ王座初防衛戦に敗れ王座から陥落。11月11日大阪府立体育会館大会と2013年2月10日広島サンプラザホール大会でリマッチに臨んだが共に敗れ、同王座をかけたタイトルマッチではK.E.S.相手に全敗となっている。　　
2014年4月にはNWA世界タッグチーム王座を獲得するも、10月にまたしてもK.E.S.に敗れ王座陥落となる。
その後はしばらくタッグでのタイトルマッチからは遠ざかっていたが、2017年3月6日大田区総合体育館で行われた新日本プロレス45周年の旗揚げ記念大会でIWGPタッグ王者矢野通、石井智宏に挑戦予定だった本間朋晃が直前の沖縄大会で怪我（パートナーは真壁刀義）をしたため、急遽代役として挑戦し見事に勝利、3年4か月ぶりの王座奪還となった。