Several people have mentioned to me that the title of Legend of the Galactic Heroes is based on a rather "interesting" translation. What would be a more accurate translation of the original title (銀河英雄伝説 Ginga Eiyū Densetsu)? I've also heard that it is based on a German title, that was then translated to Japanese, and then to English - I don't know if that is true, though.
Ginga Eiyuu Densetsu is a series of Japanese novels written by a Japanese person, and is not, to the best of my knowledge, materially based on any previously-existing work.
The 110-episode OVA series (which is probably what most viewers are familiar with) was given the alternate title "Heldensagen vom Kosmosinsel". I don't speak German, but various discussions on the internet suggest that "Heldensagen vom Kosmosinsel" is not valid German. A look at de.wiktionary.org suggests that "Kosmosinsel" is not even a word, or perhaps is a compound noun meaning "cosmos island" (which is not idiomatic for "galaxy"; that would be "Galaxie").
Given this, it looks like the producers of the OVA figured that it would look cool to have a faux-German title (in Gothic font, too!), ran "銀河英雄伝説" through Babelfish (or maybe through some dude who'd had a year of German at university), and got out "Heldensagen von Kosmosinsel". It's probably the case that the translation went Jap -> Ger (badly) and Jap -> Eng, rather than Ger -> Jap -> Eng.
I'm not sure why you've been hearing that that "Legend of the Galactic Heroes" is an "interesting" translation of 銀河英雄伝説 (ginga eiyuu densetsu), though. 銀河 ginga means "galaxy"; 英雄 eiyuu means "hero"; and 伝説 densetsu means "legend".
It's a bit contracted to omit particles, as titles often are, but the meaning is clear - this is a densetsu about the ginga eiyuus, i.e. a legend about galaxy heroes. Hence, Legend of the Galactic Heroes.
Note: in the comments, @Krazer correctly points out that an alternate parse of ginga eiyuu densetsu is as "eiyuu densetsu about the ginga", i.e. "Heroic Legends from the Galaxy". Now that I think about it, I'm not really sure which parse is actually better, in terms of the show.