Mange gader på Østerbro har navne efter danske provinsbyer. Randersgade er navngivet i flere omgange.
Den sydligste del af gaden var oprindeligt en del af Kalkbrænderivej (Se under Gammel Kalkbrænderi Vej).
Fra Nøjsomhedsvej mod nord blev vejen anlagt i 1880’erne, men først fra 1920’erne var vejen gennemgående helt til Nyborggade.
I gadens sydligste del ved Sankt Jakobs Gade, ligger Lutherkirken.
Overfor Lutherkirken ligger en bygning opført i 1880 for Det Kongelige Opfostringshus (billedet herover). Det blev grundlagt midt i 1700-tallet i Søkvæsthuset på Christianshavn, som en kostskole for drenge af enlige forældre. Det havde tidligere ligget i Store Kongensgade.
Bygningen i Randersgade blev tegnet af arkitekten Ludvig Knudsen (1843-1924). I 1952 flyttede opfostringshuset til Hellebæk i Nordsjælland, og Den Sociale Højskole overtog bygningen. I dag rummer den Heibergskolen (opkaldt efter forfatterinden Johanne Louise Heiberg), som desuden har lokaler i Blindeinstituttet på Kastelsvej.