About 150 US marines arrived on Sunday night and remained at the airport awaiting orders to deploy into the city, with a further 200 expected later yesterday.
The marines set up a security perimeter at the airport, kneeling in the grass as about 80 French marines arrived in C-160 transport planes on their way to secure the French embassy.
The initial contingent was the vanguard of a multinational force approved by the UN security council, which the US defence secretary, Donald Rumsfeld, said "will probably be less than 5,000 total". He added that the US would send up to 2,000 troops.
Colin Powell, the US secretary of state, said: "I don't think there will be a great deal of fighting, but they have to be prepared for that.
"They need to bring a sense of security back to society, as we have done in times past. Unfortunately, that security didn't stick because of the flawed politics of Haiti."
But it was the rebels - whose three-week rebellion sparked the crisis that led to Mr Aristide's departure on Sunday - who owned the streets early yesterday.
Their arrival in the capital, previously Mr Aristide's most loyal base, signalled the defeat of the pro-Aristide gangs, the chimeres .
As word spread that the rebels had arrived, thousands of residents marched towards the police headquarters waving Haitian flags and shouting: "Whether he wanted to or not he had to leave," referring to Mr Aristide.
Mr Aristide arrived yesterday in the Central African Republic and claimed he was abducted by American soldiers and forced from his homeland against his will.
In an interview with the Associated Press, Mr Aristide said: "I was forced to leave. Agents were telling me that if I don't leave they would start shooting and killing in a matter of time."
Mr Aristide gave further details of his alleged abduction in an interview with CNN, insisting that he had been the victim of a coup and that a note signed by him agreeing to stand down in the interest of the Haitian nation had been doctored.
"They didn't want to tell me where they were taking me. After spending 20 hours in an American plane, only 20 minutes before we landed here they told me that we were going to land here. The Americans were in total control. I call it a coup d'etat."
The US civil rights leader, the Rev Jesse Jackson, called on Congress to investigate the ousting of Mr Aristide.
But Mr Powell dismissed claims of abduction, saying that it was Mr Aristide who first contacted US diplomats to ask for help arranging his departure.
"He was not kidnapped. We did not force him on the aeroplane. He went on the aeroplane willingly," Mr Powell said.
"The first destination he wanted to go to would not receive him. We went through about an hour and a half of difficult negotiations with various countries and with friends of ours to find alternative locations where he might go to while the plane was in the air," he added.
With Mr Aristide gone, rebel leaders Guy Philippe and Louis-Jodel Chamblain - a former death squad leader - wearing camouflage uniforms and surrounded by armed rebels rolled into the centre of Port-au-Prince in vans, followed by throngs of dancing, cheering supporters.
Asked how the rebels would interact with the US marines, a grinning Mr Chamblain said: "They are soldiers and we are soldiers. We don't have a problem with the marines."
Colonel David Berger, commander of the US marine contingent, said the troops would "help promote the constitution and political process".
According to the Haitian constitution, in the absence of Mr Aristide, nominal authority was passed on to supreme court justice Boniface Alexandre, who was sworn in as interim leader hours after Mr Aristide left.
A tripartite commission made up of the opposition, members of Mr Aristide's government and a representative of the international community will name a "council of wise men" to run the country until elections.
Mr Powell said he did not want some of the leaders of the rebel groups to try to take any role in a new government. "Some of these individuals we would not want to see re-enter civil society in Haiti because of their past records and this is something we will have to work through," he said.