Han er utdannet offiser fra Sjøkrigsskolen og siviløkonom fra NHH fra 2000. Mellom 1985 og 2005 arbeidet Trellevik i Sjøforsvaret og Forsvarets logistikkorganisasjon, i all hovedsak med forpleining, logistikk og forvaltning. Fra 2005 til 2010 var han ansatt i kraftselskapet BKK, der han ledet et innkjøpssamarbeid mellom kraftselskapene på Vestlandet.
Trellevik meldte seg inn i Høyre i 2007 og ble valgt inn i Sund kommunestyre høsten samme år. Etter at ordfører Albrigt Sangolt døde i september 2010, ble Trellevik valgt til hans etterfølger den 8. november 2010.[4] Høsten 2013 ble Trellevik innvalgt på Stortinget fra Hordaland på utjevningsmandat. Han ble gjenvalgt i 2017 som Høyres andrekandidat i Hordaland.
