In den ersten Jahren seiner Karriere startete Preben Fjære Brynemo vorwiegend im B-Weltcup der Nordischen Kombination. Dort verbuchte er in der Saison 1997/98 den dritten Rang der Gesamtwertung. Im darauffolgenden Jahr konnte er sich noch einmal steigern und gewann die Gesamtwertung. Insgesamt konnte er zwei Tagessiege erringen.
Seine ersten Wettkämpfe im Weltcup der Nordischen Kombination bestritt Brynemo im Jahr 1999. Sein bestes Resultat in dieser Wettbewerbsserie war ein dritter Platz in einem Gundersen-Wettkampf von der Großschanze, der am 1. Dezember 2001 in Lillehammer stattfand. Dies stellt zugleich seine einzige Podiumsplatzierung im Weltcup dar.