The defendant was indicted on one of count of possession with intent to distribute more than 500 grams of cocaine, in violation of 21 U.S.C. § 841(a)(1) and 841(b)(1)(B), and for aiding and abetting, in violation of 18 U.S.C. § 2. After the district court denied his motion to suppress evidence, the defendant entered a conditional guilty plea. He now appeals the denial of his motion to suppress. We take jurisdiction pursuant to 28 U.S.C. § 1291 and affirm.

1.

On the evening of January 9, 1997, the defendant and his passenger, Felipe Garcia, stopped at a fixed checkpoint on Highway I-25, about 26 miles north of Las Cruces, New Mexico. While one border patrol agent asked the men routine questions, another agent walked a drug-sniffing canine around the exterior of the defendant’s sedan. During this canine inspection, the dog “alerted,” indicating the presence of illegal narcotics.

Based on the canine alert, the agents asked the defendant to move his car to a secondary inspection area in order to confirm the canine’s alert. The defendant consented, moved the ear, and voluntarily exited the vehicle to allow a more thorough search of the car. The dog again alerted to the inside of the ear and the defendant and Garcia were moved to a nearby trailer.

The border patrol agents were unable to locate the presence of any contraband in the vehicle. Agent Alvarado went to the trailer and asked the defendant and Garcia if they had any personal amounts of contraband in the vehicle. Defendant responded by stating: “[yjou’re not going to find anything in that vehicle.” Applt. App. at 11. At the suppression hearing, the defendant denied making this statement. In reviewing a motion to suppress, however, we consider the evidence in the light most favorable to the district court’s ruling, see United States v. Elliott, 107 F.3d 810, 813 (10th Cir.1997), md therefore must assume the statement was made.

Agent Jose Alvarado then conducted a ‘pat and frisk” of the defendant’s outer cloth[*1045] ing, which he described as “loose.” Applt. App. at 12. During the search, Agent Alvarado felt a hard object in the defendant’s waistline. The agent testified that he believed the object to be the butt of a semiautomatic handgun. The agent removed the object and found that it was a package of cocaine strapped to the defendant’s stomach. Four such packages were recovered from the defendant. Marijuana was found on the body of Garcia.

II.

When reviewing a district court’s grant or denial of a motion to suppress, we accept the district court’s factual findings unless they are clearly erroneous. See Elliott, 107 F.3d at 813. The ultimate conclusion of whether the Fourth Amendment allowed a particular stop, however, is a legal determination that we review de novo. See id.

The defendant admits that the officers had probable cause to search the vehicle. He argues, however, that under the totality of the circumstances, the agents had no authority to search the defendant’s person for illegal narcotics. Furthermore, the defendant argues that the agents cannot even make the less onerous showing under Terry v. Ohio, 392 U.S. 1, 88 S.Ct. 1868, 20 L.Ed.2d 889 (1968), to justify a pat-down search of the defendant for weaponry. According to the defendant, if the agents had truly thought that the defendant posed a threat to their safety, they would have patted him down immediately after moving him to the secondary inspection area.

We find it unnecessary to address the parties arguments on the application of Terry v. Ohio to this case because the agents were justified in conducting a full, warrant-less search of the defendant under these circumstances. The Fourth Amendment normally requires that law enforcement officers obtain a warrant, based on probable cause, before conducting a search. See, e.g., New York v. Belton, 453 U.S. 454, 457, 101 S.Ct. 2860, 69 L.Ed.2d 768 (1981). There are limited exceptions to that rule, however, one of which is that officers may conduct a war-rantless search of a person when it is incident to a lawful arrest of that person. See Chimel v. California, 395 U.S. 752, 762-63, 89 S.Ct. 2034, 23 L.Ed.2d 685 (1969). In order to be a legitimate “search incident to arrest,” the search need not take place after the arrest. A warrantless search preceding an arrest is a legitimate “search incident to arrest” as long as (1) a legitimate basis for the arrest existed before the search, and (2) the arrest followed shortly after the search. See United States v. Rivera, 867 F.2d 1261, 1264 (10th Cir.1989); cf. Rawlings v. Kentucky, 448 U.S. 98, 111, 100 S.Ct. 2556, 65 L.Ed.2d 633 (1980) (stating that where the arrest was justified before the search and the arrest “followed quickly on the heels of the challenged search of petitioner’s person, we do not believe it particularly important that the search preceded the arrest rather than vice versa.”). Whether or not the officer intended to actually arrest the defendant at the time of the search is immaterial to this two-part inquiry. See United States v. Ricard, 563 F.2d 45, 49 (2d Cir.1977).

First, we inquire as to whether the agent had a legitimate basis to arrest the defendant at the time of the search. Arrests must be based on probable cause. Probable cause to arrest exists when an officer has learned of facts and circumstances through reasonably trustworthy information that would lead a reasonable person to believe that an offense has been or is being committed by the person arrested. See United States v. Morgan, 936 F.2d 1561, 1568 (10th Cir.1991). A canine alert provides the probable cause necessary for searches and seizures. See United States v. Ludwig, 10 F.3d 1523, 1527 (10th Cir.1993). Here, the canine alerted twice to the inside of the defendant’s car. Under Ludwig, that provided the probable cause necessary to arrest the defendant. Even if the subsequent fruitless search of the car diminished the probability of contraband being in the car, it increased the chances that whatever the dog had alerted to was on the defendants’ bodies.

Second, we determine whether the actual arrest was too remote from the search. Here, the arrest occurred immediately after[*1046] the drugs were found on the defendant’s body.

III.

Given the above analysis, the discovery of cocaine on the defendant’s person was the result of a lawful search incident to arrest. We AFFIRM.