The 82-15 vote, with most Republicans joining the chamber's Democratic majority in support, launched what was expected to be an arduous legislative journey for the 1,076-page measure.
Both supporters and opponents expect the bill to pass the Senate despite fierce opposition from conservatives.
However, one GOP foe said Tuesday the Republican-controlled House would defeat it in its current form due to the pathway to citizenship.
The legislation addresses an emotionally charged issue with huge political stakes for both parties.
President Barack Obama and Democrats want to fulfill a promise to Hispanic Americans, the nation's fastest-growing demographic and a key voting bloc, to address the limbo of the 11 million immigrants living illegally in the country.
A few hours before Tuesday's vote, Obama tried to build momentum for the proposal at a White House event where he called it a commonsense approach to fix a broken system.
Addressing concerns of the measure's opponents, Obama emphasized it would increase spending on border security and require undocumented immigrants to pursue what could be a 13-year path to eventual citizenship.
"You have to pass background checks, you have to learn English, you have to pay taxes and a penalty and then you have to go to the back of the line behind everybody who has done things the right way and have tried to come here legally," Obama said.
Latino voters backed Obama over GOP nominee Mitt Romney by a 44-point margin last year, and Republican strategists are concerned about the party's long term viability in national elections if that trend holds.
In the Senate, Republicans who forced Tuesday's procedural step that required at least 60 votes to launch debate on the immigration bill joined Democrats to easily surpass that threshold.
Senate Majority Leader Harry Reid warned that some Republicans had no intention of supporting the measure even though they voted to open the formal debate and will propose amendments during the upcoming debate.
Opponents led by GOP Sen. Ted Cruz of Texas accused Democrats of insisting on the pathway to citizenship as part of the bill, knowing House conservatives won't accept it.
The goal of Democrats is to secure a popular campaign issue with Hispanic voters for the 2014 mid-term election and 2016 presidential election, he said.
"I think it's going to pass the U.S. Senate with a substantial margin," Cruz said. But "absent major revisions ... this bill will crash and burn in the House. And it is designed to do so."
Polls show many Americans favor some form of immigration policy overhaul, depending on the details of legislation.
The bipartisan proposal before Senate was hammered out this spring by the so-called "Gang of Eight" senators -- four Democrats and four Republicans.
Some congressional conservatives call opposing the "Gang of Eight" plan a matter of principle and say they won't bend.
Many consider any measure offering a path to citizenship tantamount to amnesty for those who entered the country illegally.
In addition, concerns about whether the bill will tighten security along the nation's porous borders, as asserted by backers of the plan, may make it difficult for conservatives to support it -- especially those up for re-election next year.
"The bill grants permanent legal status to millions of undocumented immigrants, as currently written, without really any guarantee of securing the border. Now, how would that possibly be a good idea?" asked Sen. John Cornyn of Texas, the chamber's No. 2 Republican, who voted Tuesday for opening debate.
Sen. Marco Rubio, R-Florida, a member of the bipartisan "Gang of Eight" who is considered a possible GOP presidential contender in 2016, argued that doing nothing amounts to what he called a "de facto amnesty" for immigrants currently living illegally in America.
At the same time, Rubio -- a popular conservative of Hispanic descent -- has made it clear that border security requirements must be toughened if he and other GOP skeptics will support it.
He is pushing an amendment that would make Congress, not the executive branch, responsible for deciding if security metrics at the border have been met before other aspects of the reform bill -- including the pathway to citizenship -- are triggered.
Because Rubio's support is so critical, other members of the bipartisan group have hinted they likely will back his proposal even though they are reluctant to make major changes to their original compromise.
The vote on the Rubio amendment will be one of the most closely watched as floor action unfolds over the next three weeks.
Other planned amendments will involve stepped-up security checks of people entering the country, temporary visas for high- and low-skilled workers, and other technical provisions.
In a rare display of unity, the U.S. Chamber of Commerce, union leaders and other interest groups have come out in support of the Senate plan.
Advocates for comprehensive reform won the first major legislative victory last month when the Senate Judiciary Committee voted 13-5 to approve the "Gang of Eight" plan.
Democratic leaders hope to have a Senate vote on final passage by the end of June.
A bipartisan group has been working on a separate immigration plan in the House, but the effort suffered a setback last week when a key member dropped out of the negotiations.
Previous efforts to pass immigration reform fell short last decade even though it was said to be a priority of President George W. Bush.
Now Obama has made the issue a major priority of his second term.
LINKS: SOURCE | Senate Bill 744 page | NYTimes list of amendment riders added to the proposal | DEBATE LIVE FEED (CSPAN2)