As he sought to distance himself from President George W. Bush and his handling of the unpopular Iraq war, now in its sixth year, McCain's two Democratic challengers repeated calls for a quick exit.
"As we all know, the American people have grown sick and tired of the war in Iraq," McCain told hundreds of veterans and families at a ceremony honouring U.S. service members killed in battle. "I understand that, of course.
"I, too, have been made sick at heart by the many mistakes made by civilian and military commanders and the terrible price we have paid for them."
Meanwhile, Democratic front-runner Barack Obama and his challenger for the party's nomination, Hillary Clinton, used Memorial Day speeches to reiterate pledges to end the war. The Democratic nominee will face McCain in the November election.
"My intention is to bring this war in Iraq to a close, and to start bringing our troops home in an orderly fashion," Obama told veterans in Las Cruces, New Mexico, a state that both parties have a chance of winning in the general election.
Wrapping up three days of campaigning in the U.S. territory of Puerto Rico, which holds its primary on Sunday, Clinton participated in a Memorial Day salute to fallen American soldiers, including many from Puerto Rico.
She also used the ceremony in San Juan to renew her call to allow residents of the island to vote in the U.S. presidential election.
"It is long past time that we give the people of Puerto Rico -- U.S. citizens all -- a full voice in a vote for commander in chief" who sends young men and women off to war, Clinton said, drawing sustained applause from the crowd, including a number of local political leaders and veterans.
Puerto Rico holds a presidential primary but its residents can not cast ballots on election day in November.
Later at a rally in Ponce, the New York senator and former first lady pledged to "bring our troops home."
The speed of drawing down the 155,000 U.S. troops in Iraq is a central issue in the U.S. presidential election. U.S. troop strength there is due to fall to around 140,000 by July.
MCCAIN'S WAR STRATEGY
But McCain, a former Navy pilot who spent 5 1/2 years in a Vietnam prisoner of war camp, on Monday warned that it would be "a mistake of colossal historical proportions" for U.S. troops to walk away before Iraq's new government gains its footing.
In a rebuke of Bush, McCain said U.S. military commanders in Iraq needed time to carry out a "counterinsurgency strategy that we should have been following from the beginning."
McCain has said he believed the Iraq war can be won by 2013, leaving a functioning democracy there and allowing most U.S. troops to come home.
McCain did not explicitly mention Obama on Monday after attacking him last week for a lack of military service.
In his speech, Obama said his grandfather served with U.S. Gen. George Patton in World War Two but admitted, "I cannot know what it is to walk into battle like so many of you."
The Illinois senator also told veterans the Democratic-led Congress would override any Bush veto of legislation that would expand educational benefits for military veterans, a bill McCain opposed. "We should make sure that today's veterans get the same benefit my grandfather got when he came back from World War Two."
McCain said he supported a different version of the bill.
Obama appeared with New Mexico Gov. Bill Richardson, a former presidential candidate who has become a vigorous supporter of him.
Obama has a seemingly unsurmountable lead in delegates to the party's nominating convention after months of contests that began in January, but Clinton has said she would remain in the race until the last votes are cast and counted.
The state-by-state nominating contests end on June 3, when 15 delegates will be awarded in South Dakota and 16 in Montana. Clinton will spend much of the rest of next week campaigning in those two states.
The Democratic nominee will likely be decided by the nearly 800 superdelegates -- members of Congress and other party insiders -- free to vote for whomever they want.