Halo 1 actually doesn't have online multiplayer. Halo 2 was the game that claimed the innovation in console matchmaking. Though the Halo 1 PC Port did have online multiplayer. Think that released months later though.
In 2002, you could play Halo 1 online using tunnel software on modded Xboxes. The trick was to make the Xbox think it was connecting to another Xbox over a LAN, when in reality, it was using a fake LAN network for online play.
The GameCube had a similar thing with Mario Kart: Double Dash!! and a program called WarpPipe.
EDIT: The Xbox program was called XLink Kai. I couldn't remember what it was called when I made the post. https://en.wikipedia.org/wiki/XLink_Kai