Po raz pierwszy na arenie międzynarodowej Preben Fjære Brynemo pojawił się podczas mistrzostw świata juniorów w Asiago w 1996 roku, gdzie wspólnie z kolegami zdobył złoty medal w sztafecie. W tym samym roku startował w sezonie 1996/1997Pucharu Świata B, w którym zajął 63. pozycję. Już w kolejnym sezonie prezentował się znacznie lepiej, między innymi dwukrotnie stając na podium: 28 lutego w Baiersbronn zwyciężył, a 14 marca 1998 roku w Štrbskim Plesie był drugi w sprincie. W klasyfikacji generalnej dało mu to trzecie miejsce. Najlepsze wyniki osiągnął jednak w sezonie 1998/1999, kiedy triumfował w klasyfikacji generalnej wspólnie z AustriakiemChristophem Bielerem.
W Pucharze Świata zadebiutował 3 stycznia 1998 roku w Schonach, gdzie zajął 17. miejsce w zawodach metodą Gundersena. Tym samym już w swoim debiucie zdobył pucharowe punkty. W klasyfikacji tego sezonu zajął 58. miejsce. Najlepsze wyniki w Pucharze Świata osiągnął w sezonie 2000/2001, kiedy zajął siedemnaste miejsce w klasyfikacji generalnej. W swoim najlepszym starcie zajął ósme miejsce 29 grudnia 2000 roku w Lillehammer. W całej swojej karierze na podium zawodów tego cyklu stanął tylko raz – 2 grudnia 2001 roku w Lillehammer, zajmując trzecie miejsce w sprincie. Uległ tylko Toddowi Lodwickowi ze Stanów Zjednoczonych oraz NiemcowiRonny'emu Ackermannowi.
Pierwszą dużą imprezą w jego karierze były mistrzostwa świata w Lahti w 2001 roku. Wystartował tylko w sprincie, zajmując zaledwie 49. miejsce. Rok później brał udział w igrzyskach olimpijskich w Salt Lake City. Wystąpił w obu konkursach indywidualnych, w Gundersenie zajmując 22. miejsce, a w sprincie uplasował się na 30. pozycji. W 2003 roku postanowił zakończyć karierę.
Salt Lake City
Samppa Lajunen
Marko Baacke
Asiago
Lillehammer
Štrbské Pleso
