Orcs are green humaniods but some Orcs have red or black skin.
They come from the world that used to be known as Dreanor and used to be a very shamanistic society. However they were then enslaved by the Burning Legion when they invaded and brought to Azeroth through the Dark Portal to wage war against the Humans. After the second war the Orcs were put in interment camps where they lost connection with there Demon masters.
Years after a brave Orc named Thrall escape from one of these camps and went off to find the rest of his people. He went to Alterac Mountains where he learnt the ways of the Shaman and swore to free his people. He then freed his people and set sail to the land known as Kalimdor. He then saved a tribe of Trolls from their island which was sinking into the sea and then helped the Tauren in Kalimdor who were losing a war against the centaurs. He then allied himself with Jaina Proudmoore and with the Night Elves they managed to win the battle for Mount Hyjal.