Griechische Seehändler aus Phokäa in Kleinasien besuchten schon im 7. Jahrhundert v. Chr. die Südküste des heutigen Frankreichs nahe der Mündung der Rhône um mit den lokalen ligurischen Stämmen Handel zu treiben. Vor allem das Zinn war als ein Bestandteil der wertvollen Bronze bei den Griechen heiß begehrt, im Gegenzug fanden feine Töpferwaren und Goldschmuck den Weg in die Häuser der lokalen Fürsten. An der schroffen und felsigen Küste waren geschützte Landeplätze rar und so steuerte man mit der Zeit immer wieder den natürlichen Hafen des heutigen Marseille an, wo die Galeeren vor Wind und Wellen geschützt waren.
Um 620 - 600 v. Chr. gründeten sie dann dank einer Landschenkung des lokalen ligurischen Fürsten an diesem Hafen eine dauerhaft bewohnte Handelspräsenz und nannten sie Μασσαλία Massalia (vereinzelt auch Massilia genannt), das heutige Marseille. Der Legende nach hatte sich eine Tochter des Fürsten bei einem großen Fest in einen der Ehrengäste, dem Anführer der griechischen Händler, Protis, verliebt. Die Beiden wurden vermählt und Sie brachte als Mitgift das Land um den heutigen Alten Hafen mit in die Ehe ein.
Der Legende nach ist die Stadt wie folgt entstanden:
Nachdem Protis an Land gegangen war, um sich mit der schönen Ligurerin Gyptis zu vereinen, ward Marseille gegründet. Protis war Phäake, und die Phäaken, dieses Seefahrervolk von der Insel Scheria, hatten nicht nur einen gastfreundlichen König namens Alkinoos, der den schiffbrüchigen Odysseus aufnahm, um ihn dann in seine Heimat Ithaka zu geleiten. Er hatte auch eine schöne Tochter. Nausikaa war es, die den gestrandeten Odysseus fand und ins Haus ihres Vaters führte. Marseille wurde also von der Liebe gegründet.
Mit der Zeit wuchst diese Siedlung zu einer großen Kolonie empor. Durch seine günstige Lage als Endpunkt der rhoneabwärts führenden Handelsstraße wurde Massalia bald zur reichsten und größten Griechenstadt am westlichen Mittelmeer. Sein Kultureinfluss erstreckte sich weit in das Hinterland hinein, und wenn sich die Helvetier zu Cäsars Zeiten der griechischen Buchstaben bedienten, so steht hinter dieser Schriftrezeption der Massailotische Einfluss. Auch in einigen südfranzösischen Dialekten scheinen sich Spuren der alten phokäischen Gräzität erhalten zu haben.
Auch Malaga, Korsika und Nizza wurden von Zuzüglern aus Phokäa besiedelt, die eine Kolonie nach der anderen gründeten. Mit der Zeit wurde Massalia so groß und bedeutend, dass es selbst Siedler ausschickte um Handelsposten und Kolonien im Westen bis hin nach Spanien zu gründen. Fast schien es so, als ob das Westbecken des Mittelmeers eine Binnensee der Phoakier und der Massalioten werden sollte, als die Koalition der Etrusker und Karthager der griechischen Expansion in der Seeschlacht bei Alalia ein Ende setzten.
Um das Jahr 545 erfolgte - nach der Flucht aus Phokaia durch Harpagos (einen Meder bzw. Perser, Statthalter des Königs Kyros) - ein erneuter Zuzug aus der Mutterstadt. (Hdt. 1,163,1-1,165,4, Solin. II,77, Liv. V,34,7-8).
Es gab immer wieder Konflikte mit den Gallien beherrschenden keltischen Stämmen.
125 v. Chr. rief Massalia die Truppen des Römischen Reiches um Hilfe gegen die Angriffe gallischer Stämme (Ligurer, Allobroger, Salluvier, Arverner und Vokontier). Im Laufe der Kriegshandlungen wurde das Gebiet um Marseille bis zur Rhônemündung von Rom erobert. Es wurde in die Provinz Narbonensis umgewandelt, und blieb bis zum Ende des Römischen Reiches dessen Bestandteil.
Anfang des 5. Jahrhunderts wurde am Südufer des Alten Hafens das Kloster Saint-Victor gegründet, das von 750 bis 960 die Residenz der Bischöfe von Marseille war. 481 fiel die Stadt an die Westgoten, 508 an die Ostgoten, 536 an die Franken und 879 an Niederburgund. Nachdem die Sarazenen sie zerstört hatten, wurde die Stadt im 10. Jh. wiederaufgebaut und den Vicomtes de Marseille unterstellt. Zwischen 1216 und 1218 wurde Marseille zur selbstständigen Republik und schließlich 1481 mit Frankreich vereinigt.
1720 und 1721 wütete die Pest, an der die Hälfte der Bevölkerung starb (50000).
Die Bevölkerung von Marseille war seit jeher stolz und unabhängig, und im ganzen Land bekannt sich gerne gegen die Obrigkeit und den König aufzulehnen. So schickte die Stadt im Jahr 1792 500 Freiwillige Kämpfer um die neue Regierung der Aufständischen während der Französischen Revolution zu unterstützen. Das von den Kämpfern aus Marseille in den Straßen von Paris gesungene Lied wurde als die Marseillaise bekannt. Am 14. Juli 1795 wurde die Marseillaise zur französischen Nationalhymne erklärt.
Im neunzehnten Jahrhundert wuchs Marseille zum bedeutendsten Hafen des französischen Kaiserreiches, vor allem auch dank der französischen Kolonialisierung in Afrika und Indochina. Die Entwicklung und Bedeutung des Hafens verstärkte sich noch mit dem Beginn der Industrialisierung, und erst recht mit der Eröffnung des Suezkanals 1869.
Am 9. Oktober 1934 fielen der jugoslawische König Alexander I. und der französische Außenminister Louis Barthou vor der Börse einem Mordanschlag zum Opfer.
Im Januar 1943 wurde nach Hitlers Anweisung ein Großteil der Altstadt von deutschen Truppen gesprengt. 27.000 Einwohner wurden aus der historische Altstadt, die als eine Brutstätte der Résistance galt, zwangsumgesiedelt. Am 27. Mai 1944 griffen amerikanische Bomber die deutschen Militäranlagen in Marseille an. Am 23. August wurde die Stadt von den amerikanischen Truppen von den deutschen Besatzern nach einwöchigen Kämpfen befreit.
Den Wiederaufbau nach dem Zweiten Weltkrieg übernahm Auguste Perret.
In der Nachkriegszeit wuchs die Stadt unaufhörlich weiter bis es dann Ende der 70er Jahre drohte im Dreck, Kriminalität und Verkehr zu ersticken. Soziale Unruhen machten sich breit und Marseille verlor innerhalb von zehn Jahren wieder 10% seiner Bevölkerung durch Abwanderung. Die Bürgermeister unternahmen in dieser Zeit große Anstrengungen um der Kriminalität, der schier unendlichen Zahl der illegalen Zuwanderer aus Nordafrika sowie dem Verfall der Stadt Herr zu werden.
1993 erschütterte ein Skandal die Stadt, als der damalige Präsident des Fußballklubs Olympique Marseille, Bernard Tapie, wegen Bestechung zum Gewinn der Landesmeisterschaft eine Haftstrafe antreten musste.
Zu allem Überfluss bereiteten die zunehmende Armut und die ausufernde Zuwanderung dem Rechtsradikalismus den Boden und Marseille sah sich weltweit in den Schlagzeilen als die hässliche rassistische Brutstätte der französischen Rechten.
In den 90er Jahren wandelt sich das Bild der Stadt, die Wirtschaft wächst wieder, neue Industrien siedeln sich an und die Stadt renoviert und baut an allen Ecken.