In the first election, held March 31, opposition candidate Ekrem Imamoglu handed a shock defeat to the government's favored candidate, dealing a blow to Erdogan's powerful Islamic-leaning Justice and Development Party.
Imamoglu, 49, a former businessman and soccer club executive, served as mayor for 18 days before Turkey's electoral board threw out the results and ordered a rerun. The governing party challenged the election on the grounds that some officials overseeing the vote were not civil servants as required by law.
The decision raised questions about Turkey's democratic process and whether Erdogan's party, which has been in control of the Turkish government since 2002, would accept any electoral loss. Erdogan launched his career as Istanbul's mayor in 1994.
Istanbul, a city of 15 million, draws millions of tourists each year and is Turkey's commercial and cultural hub. Straddling Europe and Asia, Istanbul accounted for 31% of Turkey's GDP in 2017.
Supporters surrounded Erdogan outside a suburban school where he cast his ballot Sunday.
"I believe the Istanbul voter will make the appropriate decision for Istanbul," the Turkish leader said.
In a hard-fought campaign, Imamoglu focused on urban poverty and Turkey's slide into recession. He also took aim at what he alleged was the Turkish government's use of public contracts to enrich backers of the ruling party, known as AKP for short. Erdogan's government denied the allegation.
The ruling party candidate, former Turkish Prime Minister Binali Yildirim, 63, struggled while campaigning this month to explain the need for a repeat election. He promised to improve Istanbul's infrastructure and services.
Outside a polling station on the Asian side of the city, mechanical engineer Ozlem Yasmut, 43, said the election board's decision to annul the first vote made her feel "worthless" and like she lived in a country "without justice."
She voted for Imamoglu, hoping for a city administration that would "work hard and with a sense of responsibility."
Nese Poler, 55, voted for Yildirim, saying Istanbul had been governed well under AKP-backed administrations.
"From here on, it will be even better," the homemaker said, adding that the March vote was voided because of "injustice" against the ruling party candidate.
Both mayoral candidates cast their ballots in Istanbul, visiting the polling stations with their families. They are among 21 candidates on the ballot.
Even though Erdogan was not on Sunday's ballot, analysts said the vote was a major political test for him.
"A second loss would constitute a major humiliation for Erdogan and could incite some of (his party's) old guard to come out with a new political offering," said Wolf Piccoli of the New York-based risk analysis firm Teneo Intelligence.
"Imamoglu is the first politician in almost 20 years who could become a credible challenger to Erdogan," Piccoli added.
In the March 31 vote, AKP won 25 of Istanbul's 39 districts and a majority in the city assembly. Sunday's election only repeated the vote for mayor.
In the weeks ahead of the vote, the opposition Republican People's Party, CHP, and Erdogan's AKP sponsored passionate campaigns in Istanbul and posted the faces of the two rivals all over the city. Daily election rallies had a party atmosphere.
But on Sunday customary strict election rules banned the sale of alcohol in Istanbul as well as coverage of the election by local media until after the voting ends.
Over 10 million people were eligible to vote. Polls close at 5:00 p.m. (1400 GMT) with preliminary results expected later Sunday.