1934年，比利时名侦探赫尔克里·波洛在以色列耶路撒冷哭墙旁侦破圣墓教堂的文物盗窃案，抓获身为案件凶手的本地总督察。有强烈强迫症、任何事全部要以“公平”为主的波洛打算暂时放下公事度假，渡海至伊斯坦布尔过程中首遇一起旅行的美丽家庭教师玛莉·德本海姆与她随行的黑人医生约翰·阿布夫诺特。然而，波洛刚要度假前收到伦敦的紧急电报，传唤他马上回去办理新案子，迫使波洛借助好友伯克的帮忙搭上他经营的东方快车回去伦敦，在靠近尾端的车厢中入住开始长达三天的火车旅程。
波洛在尾端餐车上结识同一车厢的乘客，一名惴惴不安的古董商人爱德华·雷切特，他当天收到几张不知名的恐吓信，打算雇用波洛来当他这三天的贴身保镖，但波洛看出他是非法商人而回绝。当天晚上，波洛睡觉时屡次听见睡在隔壁的雷切特房间里传出一系列怪声，出门望一眼时看见一个穿着红花样和服的不明人士在车厢里奔跑，直到乘务员敲雷切特房间的门时里面传出回应声音后才让波洛回去睡觉。这时，列车前方轨道因雪崩而严重受阻，东方快车所有乘客一同被困雪山。隔天早上，波洛查看没出过房间的雷切特时发现他已死在里面，身上被人连刺过数刀。为了防止前方站台的南斯拉夫警方随意在乘客中找一名替罪羊来结案，无可奈何的波洛决定和睡在其他车厢而毫无嫌疑的伯克合作办案，赶在南斯拉夫站台人员将雪堆清除之前破案。
调查尸体时，所有证据显示行凶人士只有一个人，确认火车上下没有藏人后，断言凶手就是同一车厢乘客里的其中之一。波洛从雷切特秘书麦奎因手中要到被害者收到的恐吓信时，尽量还原其中一封被烧毁的信件后，惊讶地得知雷切特真实身份其实是约翰·卡萨蒂，身为一度轰动全世界的“阿姆斯壮惨案”主凶：数年前，卡萨蒂掳走知名飞行员约翰·阿姆斯壮上校的可爱女儿黛西，即使得到索要的赎金却还是残忍杀害黛西，这场噩耗间接导致阿姆斯壮的身孕妻子索妮娅倒地流产致死，同时失去腹中胎儿而一尸两命，悲痛欲绝的阿姆斯壮最后也吞枪自杀。当这场案件审判时，阿姆斯壮家族的保姆苏珊娜被强行灌上凶手罪名，被冤枉入狱后乃至自杀身亡，更是在死后才被证明清白。波洛由此断言凶手是想替天行道，为所有因雷切特而死的无辜者们讨回公道。
波洛在尸体旁找到一张标明“H”的沾血手帕，误以为是乘客贺伯夫人的手帕，而贺伯夫人只透漏凶手昨晚曾经到过她房间、但没有看到其长相后，波洛在她房间里找到一个乘务员制服扣子。波洛想起昨晚他看见的红花样和服人士后，翻遍所有乘客行李却找不到该和服，最后还是在自己箱子里找到，由此推断嫌犯是想蒙骗他。波洛靠发现的一件疑似是凶手穿过的乘务员制服上，所留下的波本酒气味一度认定凶手是麦奎因，但阿布夫诺特医生为他提供确凿不在场证明，让波洛的推理再次陷入死胡同。这时，贺伯夫人的一声尖叫，波洛发现她后背被不明人士拿凶器刀刺入，只能重新慢慢排查所有乘客的证词。波洛调查时发现所有嫌疑人似乎都和阿姆斯壮惨案有着密切关联，当他在行李车厢请来并认定玛莉就是凶手时，玛莉只称“卡萨蒂罪该万死”。这时，阿布夫诺特枪击波洛肩膀后承认自己才是凶手，之后被伯克打倒在地，眼尖的波洛发现有着狙击手实力的阿布夫诺特对自己并没有杀意，否则不可能会射偏。
波洛将所有嫌疑人坐在铁轨隧道口的桌子前，针对卡萨蒂之死提出两个结论：第一结论是一位不知名且单独作案的凶手，伪装成乘务员搭上火车行凶后逃之夭夭；而第二结论则是凶手是除他与伯克以外的所有乘客，每人都因卡萨蒂犯下的阿姆斯壮惨案而间接承受心理包袱，因此均有杀死卡萨蒂的动机。波洛指认出贺伯夫人实为这场谋杀的主谋，识破她的真实身份是索妮娅·阿姆斯壮之母琳达·艾登。贺伯拿掉假发承认她召集在座各位共谋这起谋杀，前一晚是由玛莉穿红色和服引人注目，每人共同行凶时都在卡萨蒂身上刺一刀藉以凌迟直到他毙命；他们还为各自提供确凿不在场证明，想借此扰乱波洛的思绪，误导他推论出案件凶手是单独作案。波洛霎那间陷入左右为难，贺伯企图吞枪自杀谢罪却发现枪里没子弹，波洛承认是他想看凶手会如何反应。
东方快车再次发车后抵达南斯拉夫站台，波洛总结这起案件无法寻求到真正的公平，所有乘客都有充分行凶理由，并且自己也认同卡萨蒂确实罪有应得。因此，波洛毕生第一次选择帮凶手圆谎，对南斯拉夫警方交代凶手单独作案后逃逸的第一结论，放过全车乘客后下车。当东方快车远去时，一名英国陆军信使希望波洛能马上前去侦办一件发生在尼罗河的案件。