Nadat hij in de amateurs van Skjetten had gespeeld, werd hij in 1991 door Lillestrøm SK ontdekt. Hij speelde hier 115 wedstrijden in zes seizoenen, voor hij naar de Noorse grootmacht Rosenborg BK ging. In de 83 wedstrijden hier maakte hij zoveel indruk, dat hij in de zomer van 2000 verhuisde naar Ajax, alwaar André drie seizoenen speelde. Hij maakte zijn debuut in de met 5-0 gewonnen thuiswedstrijd tegen Fortuna Sittard op 22 augustus 2000. Meer dan een jaar later, op 25 november 2001, scoorde hij zijn eerste doelpunt voor de Amsterdamse club. Hij scoorde de eretreffer in de met 1-3 verloren thuiswedstrijd tegen PSV.
In de zomer van 2003 verhuisde hij naar Borussia Dortmund, na 66 wedstrijden voor Ajax, omdat hij onder meer door de komst van Zdeněk Grygera en Julien Escudé niet meer nodig was. In de zomer van 2005 vertrok hij naar FC Kopenhagen. In maart 2007 keerde hij terug naar zijn vaderland waar hij tot het einde van 2008 uit zou komen voor Strømsgodset IF. Hierna hing hij zijn kicksen definitief aan de wilgen.
André Bergdølmo is sinds begin 2014 hoofdcoach van Kongsvinger IL.
Noorwegen
· 
· 
