Guardiola hade vunnit sina tidigare sex matcher och 10 av sina tidigare 11 matcher i ledningen, men City spelades ut av en livlig Spurs som flyttade andra i bordet och är nu ligans enda unbeaten laget.
Spurs dominerade från början och var i fronten tidigt när Aleksandar Kolarov skar Danny Roses kors i sitt eget nät efter nio minuter.
Dele Alli bekräftade sin överlägsenhet åtta minuter före halvtid med en cool avslutning från Son Heung-mins pass.
Spurs kunde till och med ha råd med lyxen att se Erik Lamelas andra halva straff räddas av stadsbevarare Claudio Bravo, och även om Sergio Aguero två gånger förde Hugo Lloris i handling, en gång när han vände ett skott på posten, Mauricio Pochettino sida helt förtjänade en övertygande seger.
Om Liverpool tippas som potentiella titelvinnare efter sin fjärde på varandra följande Premier League seger på Swansea City på lördag, då är det positivt förolämpande att Tottenham inte höja dem till samma parentes efter denna pulserande prestanda.
Spurs tog över från första visselpipan mot en stad sida många kände var att forma upp för att springa iväg med titeln - knappt låta Guardiola sida en sekund för att andas och vägrar att ge dem någon tid att införa deras passerande spel.
Och allt gjordes utan huvudskytt Harry Kane, som är åsidosatt med en fotledsskada.
I många avseenden var detta första gången Spurs har fullt ut nått sina steg denna säsong, och vilken tid att göra det.
På dagar som detta laget som drev Leicester lång och hårt för förra säsongens Premier League titel ser hela paketet från bak till fram.
De har en pålitlig väktare i Hugo Lloris, styrka i försvar i form av Jan Vertongen och Toby Alderweireld allierade till mittfältet makt Victor Wanyama och Moussa Sissoko plus skapandet av Christian Eriksen, Alli och Son.
Detta var ett stort uttalande.
Mediauppspelning stöds inte på den här enheten
Guardiola är stolt över sin höga pressande sida och arbetar på bollen när de får besittning - de blev slagna i alla aspekter av detta av Spurs.
Ett ögonblick tidigt i andra halvlek sammanfattade hur Spurs gick till väga.
Väktare Bravo skyndade sig in i en klarering och när Nicolas Otamendi fick bollen sekunder senare, var han omgiven och skar bollen i beröring med den uppenbara glädje Pochettino.
Det är stadens första nederlag under Guardiola, så knappast tid för en massundersökning - men Spurs kan ha visat att det finns ett sätt att lösa upp hans multi-talang sida.
Spurs och Manchester City saknade båda stora spelare i Kane respektive Kevin de Bruyne - och det fanns ingen tvekan om vem som klarade sig bättre.
Det är förståeligt att Pochtino bevarade tron på den återupplivade sydkoreanske sonen. Hans energi i attack, samtidigt som han agerade som deras första försvarslinje, förebildade Spurs och passade deras stil mer än den fysiska närvaron av £ 17m sommar signering Vincent Janssen.
Staden visade den udda blixten från Aguero men Raheem Sterling kunde inte utöva något inflytande, med David Silva också marginaliserad.
Som tidigare nämnts, City förblir en trupp av hög kvalitet men hur de missade de stunder av magi som Belgien mittfälter De Bruyne kan ge för dem.
Tottenham boss Mauricio Pochettino:
"Det var en stor, stor seger för oss mot denna opposition. Jag är väldigt lycklig. Ibland när du har en plan, är det bra, ibland mindre så, men Manchester City är ett bra team. Det är svårt att spela mot dem.
"Vi måste följa detta efter den internationella matchen och vi har svårare matcher efter den internationella pausen. Om du spelar som vi gjorde idag med passion och aggression då kommer du alltid att ha en chans. Det handlar alltid om mentalitet. Det är det som hjälper oss att springa och spela som vi vill.
"Den kollektiva prestationen var stark. Det är ännu för tidigt att ta upp detta på bordet. Vi skapar fortfarande vår filosofi."
Mediauppspelning stöds inte på den här enheten
Manchester City manager Pep Guardolia:
"Det var ett tufft spel, vi visste det. Tottenham har varit ett bra lag de senaste tre åren. Vi var lite sena i alla avseenden. Vi kunde inte ha så många chanser, i många avseenden var de bättre än vi.
"Det är oktober, du kan inte föreställa dig vad mitt team redan har gjort. Jag är ny här. Hittills har det varit en fantastisk prestation men vi behöver mer, vi måste arbeta mer, det är vad det är.
"Jag trodde aldrig att vi inte skulle förlora ett spel, du kan inte föreställa dig det. Det är normalt i processen, ibland händer det och det kan hjälpa oss att förbättra oss."
Efter den internationella pausen, Tottenham möter West Brom på The Hawthorns lördag 15 oktober (15:00 BST), medan Manchester City kommer att leta efter några hem bekvämligheter på Etihad Stadium som de är värd Everton på samma gång.
Matchen slutar, Tottenham Hotspur 2, Manchester City 0.
Andra halvlek, Tottenham Hotspur 2, Manchester City 0.
Pablo Zabaleta (Manchester City) vinner en frispark på högerkanten.
Foul av Christian Eriksen (Tottenham Hotspur).
Offside, Tottenham Hotspur. Victor Wanyama försöker en genom boll, men Vincent Janssen fångas offside.
Försöket räddades. Sergio Agüero (Manchester City) höger fotad skott från mitten av lådan sparas i mitten av målet. Hjälpt av Kelechi Iheanacho.
Substitution, Tottenham Hotspur. Vincent Janssen ersätter Son Heung-Min.
Fernandinho (Manchester City) vinner en frispark i den defensiva halvan.
Foul av Georges-Kévin Nkoudou (Tottenham Hotspur).
Försök blockerat. Sergio Agüero (Manchester City) höger fotade skott utanför lådan är blockerad. Hjälpt av Nicolás Otamendi.
Pablo Zabaleta (Manchester City) vinner en frispark på högerkanten.
Foul av Georges-Kévin Nkoudou (Tottenham Hotspur).
Försök blockerat. Sergio Agüero (Manchester City) höger fotade skott från mitten av lådan är blockerad. Hjälpt av David Silva.
Substitution, Manchester City. Leroy Sané ersätter Raheem Sterling.
Utanför Manchester City. Fernandinho försöker en genom boll, men Sergio Agüero fångas offside.
Substitution, Tottenham Hotspur. Georges-Kévin Nkoudou ersätter Dele Alli.
Aleksandar Kolarov (Manchester City) vinner en frispark på vänsterflygeln.
Foul av Dele Alli (Tottenham Hotspur).
Försök blockerat. Kelechi Iheanacho (Manchester City) vänster fotade skott från vänster sida av lådan är blockerad. Hjälpt av Aleksandar Kolarov med ett kors.
Hörnet, Manchester City. Förföljd av Hugo Lloris.
Försöket räddades. Sergio Agüero (Manchester City) vänster fotade skott från mitten av lådan sparas i det övre vänstra hörnet. Hjälpt av David Silva.
Försök missade. Ilkay Gündogan (Manchester City) höger fotade skott från utsidan lådan är hög och bred till höger.
Försök blockerat. Erik Lamela (Tottenham Hotspur) höger fotade skott från mitten av lådan är blockerad. Hjälpt av Son Heung-Min.
Hörnet, Tottenham Hotspur. Sammankallad av Nicolás Otamendi.
Foul av Raheem Sterling (Manchester City).
Danny Rose (Tottenham Hotspur) vinner en frispark i defensiva halvan.
Försöket räddades. Kelechi Iheanacho (Manchester City) vänster fotade skott från vänster sida av lådan sparas i mitten av målet. Hjälpt av David Silva med en genomboll.
Fernandinho (Manchester City) vinner en frispark i den defensiva halvan.
Foul av Victor Wanyama (Tottenham Hotspur).
Utanför Manchester City. Pablo Zabaleta försöker en genom boll, men Sergio Agüero fångas offside.
Substitution, Tottenham Hotspur. Eric Dier ersätter Moussa Sissoko på grund av en skada.
Försening över. De är redo att fortsätta.
Försening i match Moussa Sissoko (Tottenham Hotspur) på grund av en skada.
Försöket räddades. Raheem Sterling (Manchester City) höger fotade skott från utsidan rutan sparas i nedre vänstra hörnet. Hjälpt av Aleksandar Kolarov.
Utanför Manchester City. Pablo Zabaleta försöker en genom boll, men Kelechi Iheanacho fångas offside.
Aleksandar Kolarov (Manchester City) vinner en frispark i defensiva halvan.
Foul av Moussa Sissoko (Tottenham Hotspur).
Försening över. De är redo att fortsätta.
Försening i match Danny Rose (Tottenham Hotspur) på grund av en skada.
Substitution, Manchester City. Kelechi Iheanacho ersätter Jesús Navas.
Tottenham avslutade välförtjänt Pep Guardiolas perfekta Premier League-start och underströk sin egen titel med en spännande seger över Manchester City på White Hart Lane.