Middelboe speelde in totaal vier interlands voor de Deense nationale ploeg, waarmee hij in 1908 deelnam aan de Olympische Spelen in Londen. Daar won de selectie onder leiding van de Engelse bondscoach Charles Williams de zilveren medaille. In de finale, gespeeld op 24 oktober1908 in het White City Stadium, bleek gastland Engeland met 2-0 te sterk. Middelboe trad bij dat toernooi op als aanvoerder van de Deense selectie, een eer die vier jaar later was weggelegd voor zijn broer Nils.