Jindřich Fügner a Dr. Miroslav Tyrš založili Sokol jako první typicky český tělocvičný spolek. Chtěli, aby prostřednictvím Sokola dospěl český národ k jakési tělesné i duchovní renesanci. Prosazovali odstranění rozdílů stavovských, politických i náboženských. Přípravný výbor Sokola, který se scházel v redakci Národních listů, se 20. listopadu 1861 obrátil na policejní ředitelství se žádostí, aby mu bylo povoleno připravovat založení spolku. Dne 17. prosince 1861 požádal Dr. Julius Grégr místodržitelství o povolení založit český tělocvičný spolek nazvaný „Tělocvičná jednota pražská“, k žádosti připojil první znění stanov, které vypracoval M. Tyrš. Za čtyři dny přišla zpráva, že stanovy musí být doplněny. Úpravy provedl opět M. Tyrš. Profesor Tonner navrhl, aby se spolek jmenoval Sokol (jihoslovanský hrdina). Všichni s nadšením souhlasili s tím, že tento název neuvedou ve stanovách, aby nepobuřovali úřady. 27. ledna 1862 došlo ke konečnému schválení a 16. února se konala ustavující valná schůze v Malypetrově ústavu.
Při volbách byl prvním starostou zvolen Jindřich Fügner. Místostarostou byl zvolen Dr. M. Tyrš a členy výboru: kníže Rudolf Thurn-Taxis, prof. Rudolf Skuherský, prof. Emanuel Tonner, ředitel plynárny Karel Šteffek, inž. František Písařovic, Dr. Eduard Grégr, sedlář Jan Kryšpín, Dr. Julius Grégr, sládek Ferdinand Fingerhut, posluchač práv Tomáš Černý (pozdější starosta Sokola pražského). Jednatelem se stal Eduard Grégr. Jako sokolský znak byla uznána červená hedvábná kokarda se sokolím pérem, v jejímž středu bylo umístěno kovové písmeno „S“, heslo vymyslel Dr. M. Tyrš: „Tužme se!“.
První cvičení proběhlo 5. března 1862 za účasti šedesáti cvičenců ve čtyřech družstvech. Cvičitelé dostávali jako plat pět zlatých za každé družstvo. Cvičitelský sbor reprezentovali: Dr. M. Tyrš, posluchač práv Jan Gross, posluchač filozofie Vojtěch Kupka, hudební skladatel Hynek Palla, právník Josef Novotný, magistrátní úředník František Písařovic a úředník c. k. pražské zastavárny Václav Špetka.
V průběhu roku 1862 vznikly jednoty v Jaroměři, v Nové Pace, v Kutné Hoře, v Jičíně, v Turnově, v Příbrami a v Kolíně. Téhož roku v červenci proběhly nové volby, protože se Tyrš s Fügnerem začali obávat o budoucnost Sokola. Byli odstraněni největší radikálové: kníže Thurn-Taxis, oba Grégrové, aj.
Počátkem následujícího roku začaly sokolům problémy s pronajatým sálem Apolla; Sokol musel do konce dubna 1863 vyklidit jeho prostory. Od 1. května do 30. září 1863 si Sokol pronajal sál v Konviktě v Bartolomějské ulici. Protože byl sál velice tmavý a nevhodný pro cvičení, navrhl Fügner postavení tělocvičny z jeho vlastních peněz. V konečné smlouvě bylo řečeno, že postaví tělocvičnu, kterou bude Sokol používat každý den od šesté hodiny večerní. Úhradu ve výši 30% zaplatí z příspěvků činných členů. Smlouva měla platit 10 let. Kdyby se Sokol před stanovenou dobou rozešel, Fügner bude mít zástavní právo na tělocvičné nářadí. Tělocvičnu postavil architekt Ignác Vojtěch Ullmann (např. palác Lažanských-dnešní kavárna Slávie, Prozatimní divadlo). Základy se začaly kopat 3. července 1863 a již 9. prosince 1863 bylo zahájeno první cvičení v tělocvičně, kde měl Fügner byt pro celou rodinu a Tyrš jeden pokoj.