1957年（昭和32年）44歳
10.3 死去したオットー・ズールの後任としてベルリン市長に選出。賛成86票、反対10票、棄権22票だった。
1957 年 10 月に市長に選出された直後、シェーネベルク市庁舎前に立つヴィリー ブラント
ベルリンSPD議長のフランツ・ノイマンが別の候補者を確保しようとしたが失敗に終わった。ノイマンはブラントの改名と、スペイン内戦中に共産主義国際旅団に参加したとされることを反対の根拠としていた。
ブラントとノイマンの対立は、異なる政治思想に起因していた。ブラントとエルンスト・ロイターを中心とする移民グループは、フランツ・ノイマンのグループの抵抗に反して、SPDの西側志向を押し通そうとした。彼らはシェパード・ストーン率いるリベラルなアメリカ占領軍将校グループに支援されていた。
ブラントは市長として、 1957年11月1日から 1958年10月31日まで、輪番制で連邦参議院議長を務めた。
ブラントは1958年と1963年に再選され、SPDが絶対多数を占めたにもかかわらず、CDU（ブラント政権I、ブラント政権II）およびFDP（ブラント政権III）と連立政権を樹立した。彼は1966年12月に連邦政府に加わるまで市長の職を務め、その後ハインリヒ・アルベルツが後任の市長となった。
1958年（昭和33年）45歳
第二次ベルリン危機。
12月7日の下院選挙の2週間前、ブラントはキリスト教民主同盟（CDU）のフランツ・アムレーン候補と対立していたが、ニキータ・フルシチョフは、ベルリンの自由都市としての地位に関する連合国間の合意が6か月以内に成立しない限り、西ドイツと西ベルリン間の輸送ルートの管理権を東ドイツに移管すると発表し、第二次ベルリン危機を引き起こした（いわゆる第一次フルシチョフ最後通牒）。
この間、ブラントは西側連合国とドイツ連邦政府に対し、西ベルリンの権利を「断固として」主張し、「ベルリンは自由であり続ける」というスローガンを掲げた。
彼は、フルシチョフの最後通牒に対する西側連合国の抵抗を形成する上で重要な役割を果たした。彼の揺るぎない姿勢は、彼を国内外で認められた人物にした。
西ベルリン市民から特に責任感のある人物と見なされた彼の態度は、1958年12月7日の選挙で功を奏し、SPDは 得票率を8.0パーセントポイント伸ばし、52.6%で絶対多数を獲得した。それでもブラントはCDUとの連立を継続した。1963年、ベルリンSPDは得票率61.9%で 史上2番目に良い結果を達成した。
1959年（昭和34年）46歳
5.1 ベルリンの共和国広場で行われた、フルシチョフの最後通牒後初のベルリン民衆による大規模集会で演説を行った。集会のスローガンは「ベルリンは自由であり続ける」だった。
11.15 SPDがゴーテスベルク綱領を採択。階級闘争の政党から国民政党への根本的な変革を成し遂げる。
この年9月にも,また57年の連邦議会選挙にも連敗したSPDは,ドイツ再統一に固執してアーデナウアーの西側統合路線に反対してきたが,59年11月バート・ゴーデスベルク綱領を圧倒的多数で採択した.「自由,平等,連帯」の民主的社会を目指し,一切の独裁体制を拒否すること,基本法を尊重し,ドイツの統一を目標とすること,ドイツの地理的・政治的状況に相応しい国防を支持し, 自由な市場経済を容認すること, などを打ち出していた. それまでの政策からの大転換であり, 「階級政党」 から 「国民政党」 への脱皮であった.
このバート・ゴーデスベルク綱領は,「Das ist der Widerspruch unsererer Zeit, der Mensch desselte Urkraft desselte und sich jetzt sich jetzt vor den Folgen furchtet.」「人類が原子の根源的な力を解放し,しかも今やその結果に恐れおののいているのは現代の矛盾である」との書きだしではじまる.なかでも 「Wettbewerb so weit wie moglich- Planung so weit wie notig!」「可能な限りの競争を, 必要な限りの計画を」の文句で有名である.
この年、外交で世界を行脚する。彼がこの年に面会したのは、アイゼンハワー大統領、ハマショールド国連事務総長、ドゴール大統領、パキスタンのアユブ・カーン大統領、ネール首相、岸信介首相、日本の天皇、オランダの女王、ノルウェー国王、欧米、アジア、アフリカの労働組合指導者、社会民主党指導者など。
長男ペーターによると、世界行脚から帰国した後、「ウィリー」はベルリンの人々から信じ難いほどの人気を得ていた。
こんなこともありました、父が日曜の散歩のとき、公共交通機関のバスの運転手と車掌にたまたま呼び止められて、政治的な憂慮や個人的な心配事についての会話に巻き込まれたことがありました。ウィリー・ブラントは当時、平民相手の護民官であったのです
当時ブラントは演説者として大きな成功を収めていた。彼はふだんは部屋に閉じこもりがちで、友人たちには「毎年五歳ずつ年老いていくようだ」と語っていた。彼は神経が鋭敏で、生い立ちや私生活に対する政敵からの攻撃に人一倍傷つきやすかった。しかし部屋から出て演説者として姿を現すと、影響力をじゅうぶんに発揮した。
演説する際に自分の心と闘っているような、言葉を自分のなかから絞り出していることがはっきりみてとれる話しぶりは、聴衆に信頼にするに足る、自然にほとばりしでる、感情を揺さぶる演説と言う印象を残した。彼の政敵ヘルムート・シュミットは、「ウィリー・ブラントは、人びとの〈たましい〉にまで迫ることができた」と語っている。
彼の人気やメディア受けのよさは、妻のルートが果たした役割が大きかった。彼女の気取りのない魅力、他人に接するときのしごく自然な心のこもったやさしさ、人の群がるセンセーショナルな場面にも物おじしない感じのよい仕草―—これらは夫のブラントにはないもので、妻のルートが広く共感をもたれる特性であった。
二人の間にはのちに歴史家となるペーター（1948年生まれ）、作家となるラース（1951年生まれ ）、俳優となるマティアス・ブラント（1961年生まれ ）の三人の息子が生まれた。仕事の多忙さから子供と過ごす時間が取れない父親だったが、ブラント一家と子供たちは新しい進歩的な家族のモデルとしてメディアの寵児ともなった。
1960年（昭和35年）47歳
11月、SPDのハノーファー党大会での執行部選挙で22番目の地位に甘んじる。選挙戦では首相候補に立てられていたにもかかわらず、こうした結果の背後にあったのは、外交政策と安全保障政策問題での意見の相違であった。旧執行部による、潜在的な後継者ブラントに対する怨念のようなものもあったとみられる。
ブラントの腹心ヘルベルト・ヴェーナーはブラントに党首の「すげ替え」を提案するがブラントはそれをきっぱり拒絶した。彼は常に力の行使を嫌い、最後まで対話と交渉の姿勢にこだわった。ブラントはのちに「ヴェーナーはあのときから、おれのことを、自分で動かせるコマとは言わないが、意気地なしだと思うようになった」と語っている。
