Die Region rund um Johannesburg ist schon seit Millionen von Jahren von Vormenschen bewohnt. Ein 3,3 Millionen Jahre alter Hominide der Gattung Australopithecus africanus, der in den Sterkfontein-Höhlen nordwestlich von Johannesburg im Jahr 1998 ausgegraben wurde, ist das bis heute älteste gefundene, vollständige menschliche Skelett.
Später, vor etwa 10.000 bis 25.000 Jahren, wurde das südliche Afrika von den San, einem Nomadenvolk besiedelt. Die San lebten in der Region um Johannesburg bis etwas in das 11. Jahrhundert nach Christus, als sie von den Bantu immer weiter in unwirtliche Gegenden verdrängt wurden.
Nachdem um 1880 zuerst in den östlichen Gebieten Transvaals um Barberton und Pilgrim's Rest Gold gefunden wurde, entdeckten Goldgräber 1886 die Hauptgoldader am Witwatersrand, die sich schließlich als das größte Goldvorkommen der Welt erweisen sollten.
Die Stadt wurde als kleine Goldgräber-Siedlung und Zeltstadt gegründet, als Gründungsdatum gilt der 4. Oktober 1886. Mit der Entdeckung des Goldes wanderten Tausende Arbeiter und Glücksritter aus England und der Kapkolonie in die burischen Gebiete ein und ließen sich in Johannesburg nieder. Innerhalb von 10 Jahren wuchs die Stadt auf über 100.000 Einwohnern heran. Der ökonomische Wert dieses Landstriches stieg rasant, was zu Spannungen zwischen den Buren, die während des 19. Jahrhunderts die Herrschaft über die Region hatten, und den Briten führte, die ihren Höhepunkt im Burenkrieg zwischen 1899 und 1902 fanden. Die Buren verloren den Krieg und auch die Kontrolle über die Südafrikanische Republik an die Briten.
Als die Briten 1910 die Südafrikanische Union ausriefen, ebnete dies den Weg für den organisierten Bergbau. Allerdings installierte die südafrikanische Regierung in dieser Zeit ein strenges Rassensystem. Die Zuwanderung von Schwarzen und Indern wurde streng reglementiert. Die schwarze und farbige Bevölkerung wurde gezwungen, in nach Rassen getrennte Gebiete, die zuvor von der weißen Regierung oft willkürlich festgelegt wurden, umzuziehen. Dadurch entstanden riesige Barackensiedlungen, die sogenannten Townships, rund um Johannesburg, von denen Soweto (South Western Townships) das Bekannteste ist. Hier lebte auch Nelson Mandela viele Jahre seines Lebens, sein Haus in Orlando ist heutzutage eine Touristenattraktion. Zudem wurde der nicht-weißen Bevölkerung verboten, qualifizierte Arbeiten anzunehmen, und zahlreiche Schwarze mussten als Wanderarbeiter in Johannesburgs Goldminen arbeiten.
Trotz dieser radikalen Trennungspolitik war beispielsweise der Stadtteil Sophiatown zu Beginn des 20. Jahrhunderts ein lebendiges Viertel der Stadt, in dem die verschiedenen Hautfarben mehr oder weniger friedlich nebeneinander lebten. Um 1950 wurde das alte Sophiatown Opfer der Apartheid-Politik der burischen Nationalpartei, die zum damaligen Zeitpunkt die Regierung Südafrikas stellte. Das gesamte Gebiet wurde zu einer "whites-only area" (Gebiet nur für Weiße) erklärt, alle Andersfarbigen zum Umzug gezwungen, und das Stadtviertel bekam fortan den ironischen afrikaansen Namen Triomf für Triumph.
1976 brachen große und blutige Unruhen in Johannesburg und von allem in Soweto aus. Der Schüler- und Studentenrat von Soweto organisierte Demonstrationen gegen die geplante Einführung von Afrikaans, die damals als die Sprache der Unterdrücker angesehen wurde, als alleinige Unterrichtssprache in schwarzen Schulen. Am 16. Juni 1976 schoss die Polizei auf eine Studenten-Demonstration. In den folgenden 12 Monaten starben mehr als 550 Menschen (zumeist Jugendliche) bei Demonstrationen gegen das Apartheid-Regime. Das bekannteste Opfer dieser Unruhen war der damals 13-jährige Hector Peterson.
Seitdem die Apartheid im Jahr 1990 abgeschafft wurde, ist auch Johannesburg befreit von diskriminierenden Rassengesetzen. Die schwarzen Townships wurden in die Stadtverwaltung integriert. Viele Vororte werden heute wieder von Menschen verschiedener Hautfarben bewohnt.
Das größte Problem des Großraums Johannesburg ist heute vor allem die Kriminalität. Als Folge wird die Innenstadt von leeren Hotels und Bürogebäuden dominiert, da viele weiße Bewohner und Firmen das Stadtzentrum aus Sicherheitsgründen verlassen haben und in die nördlichen Vororte abgewandert sind. Heute ist das zwischen Johannesburg und Pretoria liegende Midrand das Hauptzentrum für viele internationale Firmen. Das Zentrum der südafrikanischen Finanzbranche befindet sich in Sandton nördlich des Stadtzentrums.
Obwohl die Minen der Stadt schon seit langem nicht mehr gebraucht werden, da die Goldquellen erschöpft wurden und neues Gold an anderen Orten gefunden wurde, wird es in isiZulu immer noch eGoli genannt, was Platz des Goldes bedeutet.