OM have managed just three draws from their opening five Ligue 1 fixtures but Lucho Gonzalez's second-half strike gave them a deserved victory in this Champions League Group F encounter in Piraeus.
The French side had the better chances throughout and were unlucky not to be ahead by half-time after Loic Remy hit the post.
The only downside for Didier Deschamps was seeing defender Rod Fanni dismissed late on.
Indeed, the visitors could have taken the lead as early as the second minute when Benoit Cheyrou's corner was flicked on by Djimi Traore but Souleymane Diawara could not keep his header down.
Cheyrou tried his luck from distance after 15 minutes but the save was an easy one for Franco Costanzo.
In the 19th minute Kevin Mirallas got a shot in on goal after good interplay with Jose Holebas but Marseille goalkeeper Steve Mandanda turned the ball behind.
Olympiacos were threatening now and Mirallas should have done better with his shot a minute later when Ljubomir Fejsa's tenacity presented him with an opportunity.
It continued to be the French side who created the better chances though and Jeremy Morel's 20-yard strike drew a save from Costanzo in the 23rd minute.
And two minutes later the dangerous Cheyrou picked out Morgan Amalfitano who could not find the target.
Marseille were getting closer and closer, Cheyrou heading Morel's cross fractionally over the bar in the 35th minute.
And Remy was left to rue his luck two minutes later as he came inside and unleashed a shot which struck the post with Costanzo beaten.
Six minutes before the break Mirallas did well to beat two Marseille players but his shot did not match his skill and it presented Mandanda with a comfortable save.
Marseille took a deserved lead six minutes after the restart.
Morel did well down the left flank, beating Vasilis Torosidis and crossing for Gonzalez, who prodded home from close range.
Cheyrou continued to be a thorn in the side of the Greeks and his 30-yard effort in the 62nd minute was touched over by Costanzo.
The hosts rarely looked like levelling.
Jose Holebas saw his free-kick deflected over after 72 minutes, while Rafik Djebbour could not find the target from 12 yards after an inviting cross from Torosidis three minutes later, but chances were at a premium.
Substitute Fanni, who only made his entrance nine minute from the end, saw red for a late challenge on Mirallas in stoppage time, but it was too late for Olympiacos to take advantage.
And with Arsenal drawing at Borussia Dortmund, it put Marseille top of the group after one round of matches.