Khan vann med andra preferensomröstningar efter att ha misslyckats med att vinna mer än 50 procent i den första omgången.
Han sa: "Jag är så stolt över att Londonborna idag har valt hopp framför rädsla och enighet över splittring."
De grönas Sian Berry tog tredje och Lib Dems Caroline Pidgeon var fjärde. Peter Whittles femte plats var UKIP:s bästa resultat någonsin i London.
Sadiq Khans berättelse
Hur Sadiq Khan vann
Vem skulle ansluta sig till Sadiq Khan i stadshuset?
Khans framgång kommer efter en ojämn valkväll för Labour, som togs omhand av de konservativa som det näst största partiet i det skotska parlamentet, saknade majoritet i den walesiska församlingen, men behöll kontrollen över 57 råd.
Khan fick 44,3% av de första rösterna, till Zac Goldsmiths 38,6%. Efter att andra preferenser kom in i bilden fick Khan totalt 1 310 143 röster, eller 56,8 procent, till den konservativa kandidatens 43,2 procent - vilket gjorde det till en mer tydlig tävling än 2012.
EU ser att Khan blir den första muslimska borgmästaren i vilken huvudstad som helst i EU.
Utgående borgmästare Boris Johnson sade: " Många gratulationer till Sadiq för att ha fått ett enormt mandat att göra det bästa jobbet i brittisk politik. Jag önskar honom all möjlig framgång."
I ett kort tal sade Goldsmith: "Jag önskar honom lycka till, eftersom han strävar efter att bygga vidare på framgången under Boris Johnson."
Han medgav att han var "nedsatt, naturligtvis, av resultatet att jag inte kommer att kunna leverera ett manifest som jag verkligen är stolt över".
Khan gratulerades av arbetsledaren Jeremy Corbyn, som sade att han skulle arbeta med den nya borgmästaren "att skapa ett London som är rättvist för alla".
Beröm kom också in från New York borgmästare Bill de Blasio och affärssekreterare Sajid Javid, som twittrade: "Från en son till en pakistansk busschaufför till en annan, grattis".
Labour såg också ett uppsving i sin röst över hela London i valet till församlingen, medan flera framstående konservativa kritiserar sin egen borgmästarkandidats kampanj.
Före detta minister Baroness Warsi kallade det en "appelling hund visselpipa kampanj" och Ken Clarke sade att det hade varit "ett misstag" som "troligen hade en kontraproduktiv effekt".
Zac Goldsmiths egen syster, Jemima, twittrade: "Zacs kampanj återspeglade inte vem jag känner honom som - en miljövänlig, oberoende politiker med integritet."
Steve Hilton, David Camerons före detta strategichef, berättade för BBC Newsnight att de konservativas inställning till borgmästarrasen hade "fört tillbaka etiketten "nasty party" till det konservativa partiet".
Han tillade att ingen av mr Goldsmiths bästa egenskaper var "konveyed i hans kampanj, vilket jag för att vara ärlig tyckte var riktigt konstigt".
Men den konservativa församlingens ledamot Gareth Bacon berättade för BBC Radio London att påståendena om en negativ strategi var "en media-genererad fixering".
Valet var det högsta valdeltagandet någonsin på 45,6 % - en liten förbättring jämfört med 2008, då det var 45,3 %.
Läs mer om resultaten från London Assembly.
Sadiq Khan har vunnit borgmästarvalet i London och slagit den konservativa rivalen Zac Goldsmith.