The largely ceremonial upper house approved legislation passed last month by the ruling party-controlled lower house. Japan's 1947 constitution, drafted by U.S. occupation officials in the aftermath of World War II, has never been amended.
Abe applauded the approval, saying the next step is to "engage in a calm but wide-ranging debate" about possible revisions.
Abe has championed strengthening military cooperation with the United States and a more prominent Japanese role in peacekeeping, but moves to overhaul the Constitution have drawn fire from critics concerned about resurgent militarism.
Many analysts see constitutional change as a step toward a more assertive Japan that could rattle Asian neighbors still harboring bitter memories of Japanese imperialism during the past century.
"Although Japan doesn't have the intent of becoming a military power, revising the Constitution could be seen by neighboring countries as a move toward militarism," said Hiro Katsumata, a defense analyst at Nanyang Technological University in Singapore.
During Monday's vote, about 500 protesters - including Buddhist monks and students - rallied outside the parliament, accusing Abe of aiming to change the constitution to allow Japan to go to war.
Reflecting those concerns, the government stressed that there were many more steps to go before a national referendum could take place on changing the charter. Monday's legislation bans further parliamentary votes on the issue for three years.
The legislation allows the parliament to work on drafts of amendments for three years. At the end of that period, two-thirds support in the legislature, and a majority in a national referendum, would be needed to change the charter.
Constitutional revision has been a central plank in Abe's program since taking office last year. He has also enacted measures to teach patriotism in classrooms and to upgrade the Defense Agency to a full ministry for the first time since World War II.
The constitution bans the use of military force as a means of settling international disputes, and special legislation is currently needed for Japanese soldiers to participate in peacekeeping and other missions abroad.
Many Japanese credit the charter's pacifist clause - Article 9 - with keeping the country out of war since 1945, preventing a return of militarism and allowing Japan to focus on becoming wealthy.
Abe's party has promoted watering down the clause to allow more peacekeeping missions, and perhaps to let Japanese troops come to the aid of an ally such as the United States. Japan is now barred from doing so.
The opposition said the guidelines passed Monday were flawed because they did not address the issue of minimum voter turnout in a national referendum.
"Japanese constitutionalism is now facing a serious threat, and the threat arises from Prime Minister Abe's lack of understanding and lack of principles," said Kiyoshige Maekawa, an opposition Democratic Party lawmaker.
The passage was a key political victory for Abe, who has suffered from poor support ratings in recent months. His ruling Liberal Democratic Party faces crucial upper house elections in July, and some say his government's fate will depend on a decent showing in the ballot.
The conservative Abe, who has pushed for a more assertive Japanese foreign and defense policies, has argued that constitutional revision is needed to allow Japan to take a wider responsibility in maintaining global peace and security.
Tokyo has already taken steps despite the current constitutional restrictions.
It dispatched troops on a humanitarian mission to Iraq in 2004-06, the first time since World War II that Japanese soldiers have entered a combat zone. Tokyo also offers logistical assistance to U.S.-led troops in Afghanistan.
Tokyo has airlifted U.N. and coalition personnel and supplies into Baghdad and other Iraqi cities from nearby Kuwait in support of the U.S.-led war in Iraq. The mission, under way since early last year, is set to end July 31, and Japan's parliament is currently debating whether to extend it.
It is unclear how much popular support there is for Abe's program.
According to a poll released Monday, 62 percent of Japanese surveyed said they think the current government interpretation of the constitution, barring Japan from coming to the defense of an ally which is under attack, should remain intact.
Analysts said the changes could bring the constitution in line with the fact that Japan has a large military force.
"The constitution is confusing and needs to reflect current realities," defense analyst Katsumata said.