Best-picture front-runner Slumdog Millionaire scored in its first category of the night, claiming the adapted-screenplay prize for Simon Beaufoy.
The Harvey Milk film biography Milk won for original screenplay.
Cruz triumphed for her role as a tempestuous artist in the film written and directed by Woody Allen.
"Has anybody ever fainted here? Because I might be the first one," Cruz said, who went on with warm thanks to Allen.
"Thank you Woody for trusting me with this beautiful character," a teary-eyed Cruz said as she accepted the award.
The win made Cruz the first Spanish woman to win an acting Oscar, one year after her compatriot and co-star Javier Bardem won best supporting actor for No Country for Old Men.
Cruz delivered part of her acceptance speech in Spanish, saying that the win was for all the actors from her home country.
"I grew up in a place called Alcobendas, where this was not a very realistic dream," Cruz said.
Also nominated in the category were Amy Adams and Viola Davis for Doubt, Taraji P. Henson for The Curious Case of Benjamin Button and Marisa Tomei for The Wrestler.
The award was presented jointly by five actresses who had previously won the award, Tilda Swinton, Whoopi Goldberg, Goldie Hawn, Angelica Huston and Eva Marie Saint. Each actress made remarks about each of the five nominees before Swinton announce Cruz as the winner.
Cruz' win was the fifth win for supporting performers in Allen films. Past Oscar winners from Allen films include Dianne Wiest for Hannah and Her Sisters and Bullets Over Broadway; Michael Caine for Hannah and Her Sisters; and Mira Sorvino for Mighty Aphrodite
Slumdog writer Beaufoy said there are places on Earth he never can imagine being.
"For me, it's the moon, the South Pole, the Miss World podium, and here," Beaufoy said.
Milk writer Dustin Lance Black, who won with his first produced screenplay, offered an impassioned tribute to Milk, the pioneering gay-rights politician who was slain 30 years ago.
"If Harvey had not been taken from us 30 years ago, I think he would want me to say to all the gay and lesbian kids out there tonight who have been told they are less than by the churches, by the government, by their families, that you are beautiful, wonderful creatures of value, and that no matter what anyone tells you, God does love you and that very soon, I promise you, you will have equal rights, federally, across this great nation of ours," Black said.
After last year's Oscars delivered their worst TV ratings ever, producers this time aimed to liven up the show with some surprises and new ways of presenting awards. Rather than hiring a comedian such as past hosts Jon Stewart or Chris Rock, the producers went with actor and song-and-dance man Hugh Jackman, who has been host of Broadway's Tony Awards.
Instead of the usual standup routine, Jackman did an engaging musical number to open the show, saluting nominated films with a clever tribute.
Offering a nod to Slumdog Millionaire, Jackman crooned, "Just a humble slumdog, sitting in a chair, of a millionaire ..."
He hauled best-actress nominee Anne Hathaway on-stage to stand in as Richard Nixon in a gag tune about fellow best-picture nominee Frost/Nixon and asked the question in song - why don't comic-book movies get nominated? - a dig at Oscar voters' best-picture snub of the Batman blockbuster The Dark Knight.
Slumdog Millionaire went into the evening with 10 nominations and an unstoppable run of prizes from earlier film honors.
In keeping with its theme of bottomless optimism amid adversity, Slumdog Millionaire has led a charmed life, dodging a flirtation with straight-to-DVD release, winning over critics and climbing toward US$100 million hit status. The film has won top honours at all key earlier awards ceremonies.
Partial list of winners:
- Supporting Actor: Heath Ledger, "The Dark Knight."
- Supporting Actress: Penelope Cruz, "Vicky Cristina Barcelona."
- Adapted Screenplay: Simon Beaufoy, "Slumdog Millionaire."
- Original Screenplay: Dustin Lance Black, "Milk."
- Animated Feature Film: "WALL-E."
- Art Direction: "The Curious Case of Benjamin Button."
- Cinematography: "Slumdog Millionaire."
- Sound Editing: "The Dark Knight."
- Costume: "The Duchess."
- Documentary Feature: "Man on Wire."
- Documentary (short subject): "Smile Pinki."
- Makeup: "The Curious Case of Benjamin Button."
- Animated Short Film: "La Maison en Petits Cubes."
- Live Action Short Film: "Spielzeugland (Toyland)."
- Visual Effects: "The Curious Case of Benjamin Button."
