It was originally created as a result of the observation that the team that had been put together for The Dark Crystal was extremely hard to recreate for Labyrinth, since the majority of the people employed on it had gone on to other projects - since they were only employed on a contract basis. This led Henson to the conclusion that it would be a good idea to create a company that would maintain a large team on a permanent basis so that the experience (and interpersonal relationships) would not be lost between each production.
The original workshop location was at Elstree Studios, but this was a fairly typical "production-specific" setup, used for Labyrinth, at the close of production, it was decided to move the workshop away from the studios. The location chosen was on Downshire Hill, Hampstead, London, which was, not coincidentally, the same street that Henson lived on.
This was in many ways a problematic location - Downshire Hill is full of very expensive houses, and some of the processes used at the creature shop (most notably the foam latex and mouldmaking) involved foul-smelling chemicals, so the group was under a lot of pressure to change locations. There were also commercial incentives to do so, since the Downshire Hill property was quite valuable.
The chosen location had previously been used for the construction of large puppets for the film Dragonslayer (although Henson did not actually end up making the film). This was Oval Road, Camden Town - which was at the time a fairly run-down area.
The Los Angeles Creature Shop was created as an offshoot from the workshop created for the Dinosaurs TV series. It is a large workshop that creates several special puppet and animatronic creatures and characters for a large number of other films and series. The company is well-known for its more fantastic creations, like the aliens in Farscape, but it also does lifelike replications of real animals, especially when unusual animal performances are required. The company was responsible for the talking animals in Eddie Murphy's Doctor Dolittle, and won two Academy Awards for the lifelike animals in the film Babe. They are also responsible for bringing the Ninja Turtles to life in the 1990 live-action film Teenage Mutant Ninja Turtles, and its sequel Teenage Mutant Ninja Turtles II: The Secret of the Ooze as well as creating the costumes for the hit show Dinosaurs and making the "Milky" character in the Blur music video "Coffee & TV".
Despite assumptions to the contrary, Jim Henson's Creature Shop was not responsible for any of the non-human characters in the Star Wars series. The Star Wars creatures were created in-house by Stuart Freeborn in England and at Industrial Light & Magic, George Lucas' special effects shop. Jim Henson and his team, regardless were consultants for the Yoda puppets (and Frank Oz - one of the original Muppeteers - performed it), and he and Lucas did collaborate on the '80s cult classic Labyrinth.