The film opens during the first ice age where a caveman attempts to make fire with his girlfriend, however there is an earthquake that causes a cave-in that buries the two of them. This segues into a present-day Los Angeles earthquake that awakens average teenager Dave Morgan (Sean Astin) who, along with his best friend Stanley "Stoney" Brown (Pauly Shore) strive to attain popularity in high school but come off more as rejects and outcasts. Dave is in love with Robyn (Megan Ward) a sweet and attractive girl who has been his best friend since grade school, and until she reached "babehood" had been rejected by Dave on several occasions. Her boyfriend Matt (Michael DeLuise) is a dim witted jock and school bully who is constantly responsible for making both Dave and Stoney the objects of ridicule by embarrassing them in various ways, usually directly due to Dave's growing affections toward Robyn.
One day, as Dave is digging a pool in his back yard, he comes across a chunk of ice that has the body of a man in it. They leave the ice block unattended in the garage and space heaters left on cause the ice to melt, releasing the caveman (Brendan Fraser) from the opening of the film. The caveman falls head first into the 20th century, discovering a garbage truck which he misinterprets as a mammoth from his time, and television which he discovers upon entering Dave's house. When the boys return home, they find hand paint covering the walls and the house is in disarray. Upon investigating a beeping smoke alarm, they discover the caveman in Dave's bedroom, attempting to start a fire "Indian-style" by rotating a stick in the center of a pile of kindling. At first the caveman panics at the sight of them, but then Stoney quickly calms him by using the flame of a lighter to mesmerize him. After bathing him and trimming him to look like an average teenager, Dave names him "Link" as in the missing link.
They manage to fool Dave's family into thinking he is actually an Estonian exchange student sent to live with them, and enroll him in school where Link's bizarre behavior and supreme athletic skills shoot Dave and Stoney to popularity by association, allowing Dave to get closer to Robyn, to Matt's chagrin. It soon becomes apparent that Stoney's bizarre attitude is having an effect on Link's actions and speech, which causes a rift between Dave and Stoney and after a fight with Matt at a skating rink, as well as an attraction developing between Robyn and Link. Dave tries to send Link away, but a fight between him and Stoney cause Link to come running back. On prom night Link is a hit at the party with Robyn as his date while Dave stays in for the evening. Matt breaks into Dave's bedroom and steals photographic evidence that Link is a caveman, but his plan to uncover the "freak" backfires as the information instead makes Link even more popular. Dave and Robyn make up, and the three boys lead the entire prom in an impromptu caveman-like dance.
After the prom, the students attend Dave's house for a pool party where Dave and Robyn kiss. Meanwhile, Stoney and Link follow clues similar to when they found him ranging from breast prints on the slider and paint covering the walls. They follow the muddy footprints to the bathroom and discover a beautiful cavewoman (Sandra Hess) in the bathtub who turns out to be Link's girlfriend from the beginning of the film. He joins her in the bathtub as Stoney cheers them on and embraces her happily.
- Sean Astin as Dave Morgan, a tense, almost neurotic teenager who is in love with Robyn, despite losing his chance with her in grade school because he thought she was not attractive yet. He dreams of popularity more than his friends and is the most worried about being labeled as a freak if Link's secret ever got out.
- Brendan Fraser as Linkovich "Link" Chomovsky, a caveman found in the 20th Century when Dave and Stoney dig up a block of ice in which he is frozen. He is very friendly, despite also being very fierce and aggressive in his mannerisms. Still acclimating to the new world, he often misinterprets various common aspects of everyday life.
- Pauly Shore as Stanley "Stoney" Brown, a loud, obnoxious Hippie/New Wave teenager whose lease on life is profound and deeper than his thoughts seem to go. He is compassionate and quick thinking, able to soothe Link's primal instincts by showing him how to harness fire. He becomes Link's best friend and role model, eventually causing Link to imitate him.
- Megan Ward as Robyn Sweeney, a kind, compassionate girl going out with the jock bully Matt Wilson. She attempts to maintain friendships with Dave and Stoney but is often put off by their childish mannerisms, However she is already showing signs of growing tired of Matt's snobby and egotistical ways. She eventually realizes the depth of her friendship with Dave and breaks up with Matt after he starts bullying him.
- Robin Tunney as Ella, a vain, self-centered girl and Robyn's best friend. She attempts to gain Link's attention by flaunting her 'gonzagas' at him. She is rebuffed, however and learns that Link had a former love, and he has no interest in anyone else.
- Michael DeLuise as Matt Wilson, a popular jock and notorious school bully who has made it his passion in life to torment, bully and humiliate Dave. He tends to keep his distance from Stoney who merely shrugs off his intimidation attempts. He is very stuck up and the thought of Dave becoming more popular than he is causes a great deal of conflict, eventually causing him to lose the one thing Dave wants that he has; Robyn.
- Patrick Van Horn as Phil
- Dalton James as Will
- Rick Ducommun as Mr. Brush
- Jonathan Ke Quan as Kim
- Rose McGowan as Nora
- Michole White as Kathleen
- Mariette Hartley as Mrs. Morgan
- Richard Masur as Mr. Morgan
- Ellen Blain as Tenna Morgan
- Sandra Hess as Cave Nug
- Mike Diamente as Steve Morgan
- Erick Avari as Raji
- Gerry Bednob as Kashmir
Link, again played by Fraser, makes a cameo appearance in the 1993 movie Son-in-Law, which also stars Pauly Shore. Fraser also briefly appears as a soldier with the name "Link" on his fatigues in In the Army Now starring Shore.