In an African desert millions of years ago, a tribe of man-apes faces starvation and competition for a water hole by a rival tribe. They awaken to find a featureless black monolith has appeared before them. Guided in some fashion by the Black Monolith, one man-ape realizes how to use a bone as a tool and weapon; the tribe learns to hunt for food, and kills the leader of their rivals, reclaiming the water hole.
Millions of years later, a Pan Am space plane carries Dr. Heywood Floyd to a space station orbiting Earth for a layover on his trip to Clavius Base, a United States outpost on the moon. After a videophone call with his daughter, Floyd's Soviet scientist friend and her colleague ask about rumors of a mysterious epidemic at Clavius. Floyd declines to answer. At Clavius, Floyd heads a meeting of base personnel, apologizing for the epidemic cover story but stressing secrecy. His mission is to investigate a recently found artifact buried four million years ago. Floyd and others ride in a Moonbus to the artifact, which is a monolith identical to the one encountered by the man-apes. Sunlight strikes the monolith and a loud high-pitched radio signal is heard.
Eighteen months later, the United States spacecraft Discovery One is bound for Jupiter. On board are mission pilots and scientists Dr. David Bowman and Dr. Frank Poole along with three other scientists in cryogenic hibernation. Most of Discovery's operations are controlled by the ship's computer, HAL 9000, referred to by the crew as "Hal". Bowman and Poole watch Hal and themselves being interviewed on a BBC show about the mission, in which the computer states that he is "foolproof and incapable of error." When asked by the host if Hal has genuine emotions, Bowman replies that he appears to, but that the truth is unknown. Later, when Bowman questions Hal on the purpose of the mission, Hal responds by reporting the imminent failure of an antenna control device. The astronauts retrieve the component making use of an EVA pod but find nothing wrong with it. Hal suggests reinstalling the part and letting it fail so the problem can be found. Mission Control advises the astronauts that results from their twin HAL 9000 indicate that Hal is in error. Hal insists that the problem, like previous issues ascribed to HAL series units, is due to human error. Concerned about Hal's behavior, Bowman and Poole enter an EVA pod to talk without Hal overhearing, and agree to disconnect Hal if he is proven wrong. Hal secretly follows their conversation by lip reading.
While Poole is on a space walk outside his EVA pod attempting to replace the unit, Hal takes control of the pod and attacks Poole, severing his oxygen hose and setting him adrift. Bowman takes another pod to attempt rescue. Meanwhile, Hal turns off the life support functions of the crewmen in suspended animation. When Bowman returns to the ship with Poole's body, Hal refuses to let him in, stating that the astronauts' plan to deactivate him jeopardizes the mission. Bowman opens the ship's emergency airlock manually, enters the ship, and proceeds to Hal's processor core. Hal tries to reassure Bowman, then pleads with him to stop, and finally expresses fear. As Bowman deactivates the circuits controlling HAL's higher intellectual functions, HAL regresses to his earliest programmed memory, the song "Daisy Bell", which he sings for Bowman.
When Hal is finally disconnected, a prerecorded video message from Floyd reveals the existence of the monolith on the moon, its purpose and origin unknown. With the exception of one short but extremely powerful radio emission aimed at Jupiter, the object has been inert. At Jupiter, Bowman leaves Discovery One in an EVA pod to investigate another monolith discovered in orbit around the planet. The pod is pulled into a vortex of colored light, and Bowman races across vast distances of space, viewing bizarre cosmological phenomena and strange landscapes of unusual colors.
Bowman later finds himself, still in the pod, in a bedroom appointed in the neoclassical style. He sees older versions of himself, his point of view switching each time, first standing in the bedroom, middle-aged and still in his spacesuit, then dressed in leisure attire and eating dinner, and finally as an old man lying in the bed. A black monolith appears at the foot of the bed, and as Bowman reaches for it, he is transformed into a fetus enclosed in a transparent orb of light. The film ends as the new being floats in space beside the Earth, gazing at it.

Question: Where does the black monolith first appear in the story?
Answer: In a African desert.
Alternative answer: In an African desert millions of years ago, in the beginning of the story.