Frei represented Switzerland at various age levels. He played his Swiss Under-16s debut on 12 October 2004 in the 3–1 away win against the Belgium Under-16s. In 14 games for the Switzerland U-17 team he scored ten goals.
