Vid en presskonferens i Sotji erkände Cameron att de två männen var oense om hur konflikten skulle hanteras.
Men han sade att de var eniga om behovet av att få ett slut på våldet, förhindra extremism och stoppa Syriens "fragmentering".
Putin sade att de två hade ett "gemensamt intresse" av att stabilisera landet.
Samtalen, på Putins sommarresidens i Sotjis resort i Svarta havet. dominerades av den tvååriga konflikten i Syrien, där 80 000 människor har dödats.
Förenade kungariket har erkänt koalitionen av styrkor som är emot den syriska regeringen och sade att president Bashar al-Assad måste avgå som en del av en övergång till en mer representativ regering.
Av Steve RosenbergBBC News, Sotji
David Cameron flög till Sotji för att söka en gemensam grund med Ryssland på Syrien.
Det verkade inte bli något större genombrott. Vladimir Putin sade vagt att de två ledarna hade diskuterat "olika alternativ". Det fanns inga detaljer om när en internationell fredskonferens som föreslogs denna vecka av Ryssland och Amerika skulle äga rum.
Men själva samtalen signalerade en upptining i de brittisk-ryska förbindelserna. President Putin gav Cameron en rundtur i stadion som byggdes för nästa års vinter-OS i Sotji.  Och premiärministern tillkännagav ett återupptagande av "begränsat samarbete" mellan Storbritannien och ryska säkerhetstjänster för OS i Sotji.
I slutet av sina samtal berättade Kremls ledare att David Cameron hade fått en flaska armenisk konjak och att Stalin hade gett Churchill konjak 1945. Cameron svarade att han ofta sitter i Churchills studie på Chequers - och skulle hålla flaskan där som ett minne.
Storbritannien har ökat stödet till oppositionen genom att tillhandahålla pansarfordon och kroppsrustningar samt kommunikationsmateriel, och sade att EU:s vapenembargo kan behöva hävas för att hjälpa oppositionsstyrkorna.
Ryssland har däremot motsatt sig ytterligare åtgärder mot Damaskus och uttryckt oro över utsikterna till ett politiskt vakuum i händelse av regeringens kollaps och uppkomsten av islamistiska extremistgrupper.
Trots sina olika synsätt på krisen sade David Cameron att de två hade gjort "verkliga framsteg" i diskussioner som han beskrev som "väsentliga, målmedvetna och uppriktiga".
Han välkomnade Rysslands överenskommelse nyligen om att sammankalla en internationell konferens för att finna en politisk lösning på krisen.
Han sade att det fanns ett akut behov av att "bryta den onda cirkel som hotar att förstöra Syrien" och att Storbritannien och Ryssland, som medlemmar av FN:s säkerhetsråd och G8, måste ta ledningen i att hjälpa till att forma en politisk övergång.
"Som permanenta medlemmar av Förenta nationerna måste vi bidra till att driva denna process, i samarbete med partner i regionen och utanför, inte bara föra samman regimen och oppositionen vid ett förhandlingsbord utan Storbritannien, Ryssland, Amerika och andra länder som hjälper till att forma en övergångsregering som alla syrier kan lita på för att skydda dem."
President Putin sade att han och David Cameron hade diskuterat ett antal steg och alternativ för att lösa krisen,"
Han tillade att de två hade "ett gemensamt intresse av att få ett slut på våldet i landet och att inleda en fredsuppgörelse för att bevara Syrien som en integrerad och suverän stat".
Förenade kungariket har erkänt att det finns vissa extremistiska element som kämpar vid sidan av mer måttliga oppositionsstyrkor, men det sägs att endast en politisk övergång kan ge Syrien långsiktig stabilitet.
Vår korrespondent sade att mötet ägde rum i takt med att utvecklingen, inklusive israeliska flyganfall mot mål i Syrien och oron för eventuell användning av kemiska vapen, riskerar att föra konflikten in i en ännu farligare fas.
De syriska myndigheterna säger att Israels strejker mot armémål denna månad visar att det samordnar sig med militanter för att destabilisera regeringen, men Israel sade att det var riktat mot vapen som är bundna till Hizbollah-militanter i Libanon.
Vladimir Putin, som talade om förbindelserna mellan Storbritannien och Ryssland, sade att den bilaterala handeln och det vidare samarbetet ökar, och London och Moskva skulle samarbeta för att utveckla " lovar" energiprojekt.
David Cameron sade att de två länderna fortfarande har skillnader, men att ett mer effektivt förhållande skulle göra medborgarna i båda länderna "säkrare och bättre".
Storbritannien kommer att ge "begränsat" säkerhetsstöd till vinterolympiaden nästa år i Sotji, avslöjade premiärministern.
Förbindelserna mellan Storbritannien och Ryssland var ansträngda under många år efter den ryske dissidenten Alexander Litvinenkos död i London 2006 - en period då det inte fanns några möten mellan Vladimir Putin och högre brittiska ministrar.
Men Cameron besökte Moskva 2011 och Vladimir Putin kom till London förra året, där de två såg en judo bout vid OS, eftersom länderna försökte bredda sina handels- och säkerhetsförbindelser.
Premiärminister David Cameron har sagt att världssamfundet måste göra mer för att "hjälpa till att forma" en övergångsregering i Syrien efter att ha fört samtal med Rysslands president Vladimir Putin.