Onder leiding van bondscoach Nils Arne Eggen maakte Flo zijn debuut voor het Noors voetbalelftal op 6 mei1987 in het olympisch kwalificatieduel tegen Turkije (1-1) in Moss, net als Erland Johnsen (Moss FK) en Olav Klepp (Brøndby IF). Hij nam in dat duel de enige Noorse treffer voor zijn rekening. Rushfeldt speelde in totaal 53 interlands en scoorde elf keer voor zijn vaderland. Hij nam met Noorwegen deel aan het WK voetbal 1994 en het WK voetbal 1998.