1949年，国际奥委会在罗马举行第四十四届全会，投票选择第十六届奥运会的主办地点。当时提出主办申请的候选城市有墨尔本、布宜诺斯艾利斯、墨西哥城及6个美国城市。随着墨西哥城及6个美国城市被淘汰，进入第三轮角逐的仅剩墨尔本和布宜诺斯艾利斯。最后，墨尔本以一票的优势险胜布宜诺斯艾利斯，得到主办权，使奥运会第一次落户世界的第五个大洲。然而，南北半球季节的差异成为大问题，北半球的夏天正是澳大利亚的冬天。为了避免在冬天举办奥运会，墨尔本奥运会组委会曾提出将该届奥运会放在1956年2月举行，此时正是澳大利亚的盛夏。考虑到2月正是大多数国家赛季结束之后的休整阶段，运动员处于竞技状态的低潮期，国际奥委会没有同意。反复权衡之后，国际奥委会决定在11月22日至12月8日举办第十六届奥运会。为适应这个史无前例的奥运比赛日期，各国运动员被迫在1956年调整自己的训练和比赛周期，有的国家干脆人为地推迟赛季。
不寻常的比赛时间加上不寻常的国际政治背景，使得墨尔本奥运会笼罩在阴影之下。继美国1954年爆炸第一颗氢弹之后，苏联也于1955年爆炸了氢弹——当各国奥运选手挥汗如雨地进行训练时，两个超级大国正在加紧扩军。世界坐在一个巨大的火药桶上。1956年夏，波兰局势动荡；1956年10月底，苏军出兵匈牙利。
不仅欧美政局不稳，非洲、亚洲同样没有安宁。纳赛尔出任埃及总统之后，美国和英国抽回了建设阿斯旺水坝的经济资助。作为报复，纳赛尔总统宣布没收苏伊士运河集团的资产，以此弥补阿斯旺水坝建设资金的不足。在英法两国的支持下，以色列出兵西奈半岛，并迅速向苏伊士运河方向推进，导致苏伊士运河战争爆发。随着苏联表示将站在埃及方面参战，英国、法国也威胁要帮以色列打仗。
错综复杂的国际局势直接威胁到1956年奥运会：战火之中的埃及和以色列、伊拉克、黎巴嫩，先后宣布放弃参赛；佛朗哥军政权统治下的西班牙，也放弃了组团去墨尔本的机会；为抗议苏联出兵匈牙利，荷兰奥委会于开赛前16天宣布抵制奥运会，撤回已经抵达墨尔本的部分运动员。
在抗议苏军出兵匈牙利的问题上，瑞士考虑良久，难以定夺。在距奥运会开幕只有12天的时候，才决定前往墨尔本参赛。但瑞士的决定作得太晚。机票方面的困难，使得瑞士代表团无法在报到截止日之前赶到墨尔本。这样，瑞士人违心地放弃了这届奥运会。
由于当时国际奥委会在承认中华人民共和国的同时，同意中国台湾以“中华民国”名义参加1956年奥运会，中华全国体育总会在反复与国际奥委会交涉无效的情况下，于1956年11月6日声明放弃参加墨尔本奥运会；1958年8月19日，中华全国体总又正式宣布断绝同国际奥委会的一切关系，并退出接纳中国台湾为会员的8个国际体育联合会，以抗议有人制造“两个中国”的用心。
墨尔本奥运会开幕之前，几乎没有什么令人振奋的消息。惟一还能给人们带来一丝安慰的，是国际奥委会成功地解决了复杂的德国问题。布伦戴奇是一个理想主义者，他以当时看来近乎天方夜谭的办法，把分裂的两个德国和独立的萨尔州整合在一起，组成了统一的德国代表团参加墨尔本奥运会！
1955年6月18日，国际奥委会在巴黎召开第五十届全会。会上以27票赞成，7票反对通过了对民主德国奥委会的暂时承认。暂时承认的前提是，两个德国必须组成统一队参加墨尔本奥运会，否则暂时承认便立即中止。经过漫长的谈判，两德终于组建了包括139名联邦德国队员和37名民主德国队员的统一队。上届奥运会时单独参赛的萨尔地区也被布伦戴奇纳入了德国统一队的行列。布伦戴奇是英明的——墨尔本奥运会结束不到一个月，萨尔地区就经过全民公决回归了德国。
统一的德国代表团三方谈判商定：由队员多的一方担任代表团团长（担任这届奥运会德国代表团团长的是联邦德国的施多克——作者注）；由于两德的国旗都是黑红金底色，双方商定使用带有奥林匹克五环的黑红金三色旗作为统一队队旗；颁奖仪式上使用贝多芬第九交响乐中的《欢乐颂》替代国歌。
两德问题的成功解决，诞生了令全世界跌破眼镜的“德国模式”。前国际奥委会主席基拉宁勋爵在回忆录中写道：布伦戴奇也曾想应用“德国模式”处理中国问题，但没有获得成功。1988年奥运会前，韩朝双方曾谈判试图沿用布伦戴奇的“德国模式”，遗憾的是也未能成功。但在外交官出身的国际奥委会主席萨马兰奇的斡旋之下，朝鲜和韩国成功地运用“德国模式”参加了2000年悉尼奥运会：用朝鲜半岛标志代国旗，以民歌“阿里郎”代国歌，为促进朝鲜半岛最终走向统一增加了一份推动力。
除了国际政治背景错综复杂而导致墨尔本奥运会前景黯淡之外，其他的客观因素也给主办者增添了很多麻烦：其一，路途遥远，费用昂贵，使得许多国家的奥委会尽力减少代表团人数。与赫尔辛基奥运会参赛总人数相比，本届奥运会的数字大大下降；其二，澳大利亚政府对马匹进关检疫的严格规定和漫长周期，使得国际奥委会执委不得不于1954年在斯德哥尔摩会议上决定，将全部马术比赛转移到瑞典斯德哥尔摩进行——倘若国际奥委会事前知道澳大利亚对马匹检疫的繁杂程序，墨尔本可能根本无法获得1956年奥运会的举办权；其三，也是最要紧的一点，墨尔本根本就没有奥林匹克体育场。
墨尔本市长彪雷派尔曾经是奥林匹克选手，参加过从1908年至1924年间的4届奥运会，并获得过3枚游泳奖牌。他本人亲自出任墨尔本奥运会的组委会主席，承诺一定要修建一个奥林匹克体育场。为了履行承诺，组委会决定耗资25万英镑改建一个澳式橄榄球的比赛场，增铺跑道，将4万观众席扩建到10万。此外，组委会耗资125万英镑修建了一个包括游泳馆、田径场、自行车赛场和曲棍球场的奥林匹克公园；耗资200万英镑修建了奥运村。击剑、体操、举重、摔跤、拳击等项目的比赛则被安排在现有的场馆中进行。赛艇、皮划艇的比赛地点在距墨尔本124公里外的文斗雷湖。由于该比赛地点距奥运村太远，组委会破例为这两个项目的选手又修了一个小型奥运村。
就在墨尔本奥运会准备工作即将就绪之时，市长兼组委会主席彪雷派尔先生不幸去世。与4年前大放异彩的赫尔辛基奥运会相比，墨尔本奥运会的前奏曲实在是低沉和黯淡。
