A use of the term 'space marine' that predates Games Workshop's by fifty-one years.
However, GW's mailed power gauntlet came crashing down on SF author MCA Hogarth when she published a book called Spots the Space Marine. GW asked Amazon to remove the book from their website and informed the author that she was not allowed to use the term in either the title or text of her book. Hogarth, who is not very wealthy, declined to fight the claim legally but has publicised it, which has led to significant discussion of the subject by sites such as Boing Boing and Scalzi's Whatever (and Scalzi is taking it up with the influential Science Fiction and Fantasy Writers of America guild, of which he is president). This site also has interesting information for those Games Workshop customers - and that includes anyone who has bought a Black Library novel or Relic WH40K computer game - who wish to protest directly to the company.
Games Workshop's use of 'Space Marines' began in 1987 with the publication of the first edition of the Warhammer 40,000 miniature combat game.
A quick survey of the internet discovers these examples of use prior to that time:
- A short story called Captain Brink of the Space Marines, published in Amazing Stories in 1932.
- A sequel to the above, The Space Marines and the Slavers, published in Amazing Stories in 1936.
- E.E. 'Doc' Smith's Lensman series mentions space marines in Galactic Patrol (1937-38) and Grey Lensman (1939-40) in passing before they actually appear in First Lensman (1950).
- Robert Heinlein's short stories Misfit (1939) and The Long Watch (1941) both feature the phrase. Whilst it doesn't mention the phrase directly, the novel Starship Troopers (1959) is considered the definitive portrayal of space marines.
- H. Beam Piper's Space Viking series of SF novels (beginning in 1963) use characters who strongly resembler space marines.
- The roleplaying game Traveller, which debuted in 1977 and was partially inspired by both Piper and Heinlein, also used similar concepts. It should be noted that Games Workshop was originally founded in 1975 as importers of US roleplaying and wargame materials, including the original Traveller upon its release.
- A popular 'filking' song at American SF conventions in the 1970s was 'Outer Space Marines', created by Jeff Duntemann.
- Fantasy Games Unlimited released a miniature wargame called Space Marines in 1977.
- The popular anime series Space Battleship Yamato (1974-1980) directly uses the phrase. The English-language version, Star Blazers, first appeared in 1979.
- A song called 'Space Hero', by Julia Ecklar, released on her 1983 album Space Heroes and Other Fools, uses the term 'space marines' in its lyrics.
- The movie Aliens, released in 1986, features a Colonial Marine Corps. Director James Cameron had the actors read Starship Troopers as part of their training for the roles. The same term was later used for the ground component of the Colonial military in the newer Battlestar Galactica (which debuted in 2003).
A tactical miniatures game called Space Marines, released ten years before WH40K.
There is also the small matter of Games Workshop not attempting to protect the alleged trademark prior to this point, namely not when Dark Horse released a number of Alien comics and magazines in the early 1990s which sometimes used the term 'space marine' to refer to the Colonial Marines. They have also taken no action against Barnes and Noble, which has a sub-section called 'Soldiers and Space Marines'.
More notably, GW has not attempted to sue Blizzard Entertainment, despite the latter's creation of the StarCraft franchise in 1998 which is - sometimes breathtakingly - similar to Warhammer 40,000. The Terran Marines in StarCraft not only fulfil the same role as the Space Marines in WH40K but look extremely similar. Coincidentally, Activision-Blizzard is a multi-billion-dollar company with legal resources that vastly outstrip those of GW's by several orders of magnitude.