Winner of So You Think You're Funny? in 1994, Martin has gone on to write additional material for shows such as Head on Comedy, Lenny Henry in Pieces and Haywire, and comedians such as Harry Enfield, Johnny Vaughan and Phil Kay. The Lenny Henry special which he contributed to was winner of the Golden Rose of Montreaux in 2001. He had also worked with Lee Evans, in 1995.
Trenaman is good friends with Bill Bailey and has been credited with writing material for Bailey's shows Is It Bill Bailey? and Never Mind the Buzzcocks, he has appeared in two of Bailey's live shows; with Phil Whelans in Bill Bailey's Cosmic Jam (1996) as part of the band "The Stan Ellis Experiment", and in Part Troll (2004) with Kevin Eldon and John Moloney in Kraftwerk spoof, "Das Hokey Kokey". He also appears on Bailey's Bewilderness DVD in the spoof interview Legacy of Dreams: With Martin Trenaman. Along with Bill Bailey, Phil Whelans, and Kevin Eldon, Martin is a member of punk rock cover band Beergut 100.
He has also worked with Sean Lock, both in writing additional material for Is it Bill Bailey? and Never Mind the Buzzcocks, and also by co-writing Sean Lock's sitcom 15 Storeys High. Martin has contributed to all 4 series of the show, which includes 2 on radio and 2 on television. He also co-stars in the first series of the radio show, and makes numerous guest appearances during the television series.
Martin has also had cameos in scores of British comedy series, including Barking, The Nearly Complete And Utter History Of Everything, The Strangerers, World of Pub, Saxondale, Wild West, TLC, He Says, She Says and The Mighty Boosh. He also appeared in an episode of Spaced as Derek, the nemesis of Bill Bailey's character Bilbo Bagshot. He played Tony Hancock in Kenneth Williams: Fantabulosa!, in 2006.
He appeared in an advert for mobile phone company 3, advertising 3G video messaging by talking to a hand puppet in the shape of a duck. He also did the voiceover for an AA advert. He featured as a voice over artist on the 30 November 2007 edition of Never Mind the Buzzcocks, which also featured his Mighty Boosh co-stars Noel Fielding and Rich Fulcher. He also appeared in BBC1's The Impressions Show, presented by Debra Stephenson and Jon Culshaw.