The border gateway protocol (BGP) is used to exchange network reachability information between autonomous systems, but it is threatened by man-in-the-middle attacks. Therefore, an improved certificateless multi-signature scheme is proposed and applied to BGP. The inter-domain routing must be signed according to the route delivery order, and the autonomous systems can receive the route only after the multi-signatures are verified successfully. The public and private keys to the autonomous systems are generated interactively with the trusted center with a fixed length of the signature message and efficient calculations. The security analysis proves that the proposed scheme cannot be fabricated under the random oracle model and is valid for resisting the man-in-the-middle attacks on BGP.