RFSL grundades på ett möte den 21 oktober 1950 som en avdelning av danska Forbundet af 1948. I protokollet från mötet framgår att 36 medlemmar, 35 män och en kvinna, hade samlats ”hos vännen G-A. Petersson i Solna”. Initiativet var Allan Hellmans, som varit den förste med att i svenska media öppet berätta om sin homosexualitet. I ett reportage i tidningen Se 1951 kallades han ”Sveriges modigaste man”.
Två år senare, 1952, bildades RFSL som en egen organisation där målgruppen var homosexuella. Den första ordföranden var Owe Ahlström.
RFSL är med sin långa historia en av världens äldsta organisationer som arbetar för homo-, bisexuella och transpersoners rättigheter i samhället.
I början av femtiotalet hade RFSL verksamhet i Stockholm, men även i Göteborg, ”Friends Club”, och 1957 bildades formellt två avdelningar i Stockholm, ”Diana”, för kvinnor och ”Kretsen”, för män. I början av sjuttiotalet hade en mängd avdelningar bildats och organisationen formaliserades genom att dessa fick namn utifrån orten, såsom RFSL Gävle och RFSL Borås. Samtidigt, påverkade av Stonewall-revolten i New York, tryckte nya unga medlemmar på för att göra RFSL mindre försiktiga i sitt arbete för homosexuellas rättigheter.
RFSL ungdom bildades först 1999 även om ungdomsgrupper varit verksamma redan under åttiotalet.
RFSL:s första egna lokal kallades ”Timmy” och låg på Timmermansgatan i Stockholm och invigdes 1964. Både RFSL Förbundet och RFSL Stockholm flyttade i slutet va 80-talet till stora tjusiga lokaler, inkluderat en klubblokal, på Sveavägen. Efter att klubblokalen blivit till en mataffär, RFSL Stockholm flyttat till Alsnögatan på Söder så lämnade RFSL för ca ett år sedan med sitt förbund slutligen Sveavägen helt för att idag husera i Posthuset på Vasagatan 28 i Stockholm.