The eviction took place without any casualties a statement from the office of Spanish Prime Minister Jose Maria Aznar said.
Perejil has been at the centre of a spat between the two countries since 11 July when Morocco sent a dozen Moroccan soldiers to occupy the uninhabited island.
Late on Tuesday the Spanish Government recalled its ambassador to Morocco, Fernando Arias Salgado, after Rabat failed to respond to a letter from Madrid urging the Moroccans to vacate the island.
Click here for a map of the area
On Tuesday the team of Moroccan soldiers who had set up camp on the island were seen collecting supplies from a Moroccan navy ship.
According to the statement from Mr Aznar's office, Spain took action after consulting with the UN Security Council and the country's allies.
"The Spanish government has found itself obliged to order an eviction of the Moroccan detachment established on Perejil Island," the statement said.
The operation took place at about 0615 (0415 GMT) and involved naval units, special ground forces and combat aircraft, Spanish media reported.
Taken prisoner
Six Moroccans were taken prisoner and moved to the Spanish enclave of Ceuta, just five kilometres (three miles), from the island, but they were repatriated a few hours later.
By midday two Spanish flags could be seen flying above the island in place of the Moroccan one that the troops had raised.
Perejil island
At least a dozen Spanish soldiers had taken up positions on the island's perimeter, as five warships patrolled nearby.
Despite a military build-up in the area Spain had given no public warning that the troops might be removed by force.
Government officials on both sides had repeatedly said they wanted a diplomatic solution to the crisis.
Extra warships
On Wednesday, Spain deployed a fifth warship to the waters near the island.
Defence Minister Federico Trillo said the frigate Castilla would arrive in Ceuta on Wednesday.
Despite the military action the Spanish Government said it wanted "to maintain fruitful, friendly and co-operative relations" with Morocco and said it was willing to hold talks to achieve this.
The small rocky island lies within Moroccan territorial waters, just 200 metres (220 yards) off the Moroccan shore in the Straits of Gibraltar, but has been Spanish territory since 1668.
Morocco says it sent the troops to Perejil as part of efforts to crack down on terrorism and illegal immigration.
200m off the Moroccan shore in the Straits of Gibraltar
Less than 1km in diameter
Rocky and uninhabited
Visited by herdsmen who take their goats to graze
Named after the wild parsley which grows there - Perejil means "parsley" in Spanish
Known in Morocco as Leila
Related to this story:
Analysis: Spanish or Moroccan land?
(16 Jul 02 | Europe)
Spain recalls envoy in island row
(17 Jul 02 | Europe)
Spain's North African enclaves
(16 Jul 02 | Europe)
Tensions over 'Parsley' island
(15 Jul 02 | Europe)
Analysis: Spain and Morocco raise the stakes
(12 Jul 02 | Europe)
Spain's immigration 'stepping stone'
(28 May 02 | Europe)
Internet links:
Spanish Government
|
Moroccan Communications Ministry
The BBC is not responsible for the content of external internet sites