史密斯想想建立一个公司，连夜快递小包裹，在美国广袤的土地上，利用军用、民用领域都已经普及的航空运输来实现“次日送达”。1971年，27岁的史密斯在孟菲斯带着他的计划出席了家庭基金 ——弗里德里克·史密斯企业公司的董事会，为他酝酿已久的创业计划投入了全部850万美元家产，并从投资者和银行筹款，总额达到了9000万美元。这是美国商业史上金额最多的一次单项投资。1971年6月1日，联邦快递公司（FedEx）在美国阿肯色州小石城正式成立。
史密斯认为航空运输有其不可替代的优势。在当时的美国，工业分散现象明显，大企业纷纷开始全国甚至全球化布局工厂，以实现原料、劳动力、产品、市场的综合效益。而其中间的遥远距离需要快速的运输来达到最佳效果的实现。航空运输正是填补这一短板的有力途径。
然而创业伊始，联邦快递就遭受了阻碍。由于小石城机场的官员拒绝为公司提供设施，联邦快递不得不在1973年迁往田纳西州孟菲斯。直到1973年4月17日，联邦快递才得以开始正式营业。迁往孟菲斯后，联邦快递开始为25个城市提供空运快递服务。不过作为航空快递行业的拓荒者，转移阵地的联邦快递还是遇到了重重困难。
史密斯本将所有的希望寄托于公司的第一个大客户——美国联邦储备系统。史密斯认为联邦快递独到的隔夜传递可以为对方节省大量的金钱与时间，对方没有理由拒绝这种先进的服务。就连公司的名称“联邦快递公司”都是因此而命名的。因此，信心十足的史密斯向泛美航空公司购买了两架装有涡轮风扇发动机的达索尔特鹰式飞机，并将它们改装成货机。可是万万没想到，联邦快递的这个计划动了原先物流环节的饭碗，遭到了联邦储备系统的否决。再加之当时美国严格的航空管制法，联邦快递很快就出现了巨额亏损。营业短短几个月后，1973年7月，公司已经亏损了数千万，同时还有数千万的负债，深陷绝境。
为走出困境，弗雷德里克·史密斯四处拜访投资人，寻求外部资金支持。但没有人愿意趟这摊浑水，投资人纷纷拒绝了史密斯的要求。7月中旬，史密斯和他的联邦快递只剩下了5000美元资金，面对必须要支付的24000元航空燃油账单，史密斯束手无策。在芝加哥拜访投资人的再次失败让史密斯狠下心“另辟蹊径”。他没有返回孟菲斯总部，而是直接前往拉斯维加斯，带着仅剩的5000美元走进了赌场，与命运进行一场你死我活的豪赌。
周一，当史密斯再次出现在孟菲斯的公司总部时，公司已经有了32000美元资金。公司靠着这笔赌来的资金得以又坚持了一周。然而就在这一周内，联邦快递终于迎来了及时雨，获得了1100万美元融资。获得融资的联邦快递仿佛重获新生。
为了一步步支撑着航空管制法下艰难生存的联邦快递，弗雷德里克·史密斯简直堪称不顾一切、孤注一掷。他不仅不择手段地寻求投资家的帮助，还想尽一切办法将所有能拿出的家产拿来铺就这条创业之路。史密斯甚至伪造律师签名，将属于两个姐姐名下的家族基金归为己有，并为此惹上了官司。然而偏执也好，恒心也罢，史密斯的投入终于获得了回报。
此时的美国社会面临巨大变动。由于美国政府的行业管制政策过于盛行，企业的自由发展受到了严重制约。政府直接干预市场进入和企业定价的行为，不仅阻碍了企业家的创新精神，更助长了官僚主义，导致政府管制机构的僵化和无能。因此，严格的管制政策也在社会舆论的压力下逐步放松。1974年，美国航空管制政策逐渐松动，联邦快递公司的外部经营环境明显改善。到了1975年7月，创业四年的联邦快递终于实现了首次盈利。1977年，联邦快递营业收入突破1亿美元，获纯利820万美元。大难不死的联邦快递终于起死回生。
70年代末，美国掀起了以放松管制为主要内容的规制改革运动。而这一运动首先就在民航业取得了成功。政府在民航业引入市场竞争机制，不再用行政审批的办法来干预民航的票价和市场进入，投资人也可以决定是否组建新的航空公司。1978年，美国总统卡特最终宣布解除航空管制法。属于联邦快递和航空物流行业的春天终于到来了。联邦快递的逆境重生，也成为了风险投资案例的一个奇迹。
解除航空管制法为美国的民用航空运输打开了枷锁，让联邦快递的运输成本大大降低。而相似成本的比较下，航空运输的快速及时性使之很快成为联系美国东西部的重要选择，联邦快递的市场逐渐打开局面。而相反，一些传统的依靠陆地运输的快递公司却因为市场份额的大幅减少，逐渐萎缩甚至破产。联邦快递的竞争对手物流巨头UPS，身陷罢工浪潮；而另一竞争对手铁路快递公司（REA），在航空管制法解除后濒临破产。行业外部经营环境的改善和内部竞争对手的衰退，让联邦快递迈入了发展的快车道。公司为全国各地的客户运送零件、血浆、移植器官、药品等各种需要迅速运递的物品，业务量一路飙升。1978年，联邦快递正式上市，一跃成为全球航空货运公司的领头羊。
进入80年代，联邦快递又在航空运输业中取得了一次重大胜利，他们收购了自己最大竞争对手——飞虎国际公司。飞虎国际公司比联邦快递公司早20年进入航空货运领域，是当时全球最大的重量货运公司。第二次世界大战结束后，几个战时飞行员创办了飞虎国际公司，让飞虎成为了美国最早涉足民用航空运输的企业之一。到1988年，飞虎公司已拥有22架波音747型飞机、11架波音727型飞机和6架DC-8型飞机，拥有雇员6550人，年度营业收入为14亿美元。然而就是这样一个根正苗红的行业巨头，内部管理因循守旧，到80年代末期，公司问题已经日益严重。机械设备逐渐老化、落后，而财务支出却毫不收敛。员工也逐渐习惯养尊处优，要求涨薪。1984年，飞虎公司第一次出现了财务赤字。80年代，联邦快递的战略重心转移到国际市场，而飞虎公司最具有吸引力的是在过去40多年中建立起来的国际航线，史密斯决定收购这一老化而对自己拓展颇有价值的竞争对手。，遭到了拒绝。这一大规模的收购也引发了诸多争议。业界广泛认为这是联邦快递的又一次豪赌，认为飞虎这个困难重重、问题成山的企业会让联邦快递这个充满创新精神的公司饱受拖累。就连史密斯的工业顾问伯纳德·拉朗德都说：“必须像处理两头豪猪交配那样十分小心地对待这种合并，联邦快递公司在玩赌注很大、风险也很大的赌牌。”然而史密斯再次以惊人的毅力敢于经受风险。麦尔柯快递公司，将其旗下遍及全球80多个国家和地区的服务网络化为己有，从而让业务伸展到荷兰、英国以及阿拉伯联合酋长国等地区。这样一来公司内部团结一心，专注于国际业务的拓展。而飞虎公司最具有吸引力的是在过去40多年中建立起来的国际航线，当时，飞虎公司号称在21个国家里拥有长达45年以上的航空权和降落权。80年代，联邦快递的战略重心转移到国际市场，让整个公司上下更加专注于对飞虎国际公司的收购进程。
史密斯和他的联邦快递终于等来了机会。1988年末，飞虎国际航空公司的最大股东、信实金融服务公司董事长索尔·斯坦伯宣布收购不在他名下的飞虎公司83%的股份。史密斯立即提价加入角逐。最终，史密斯在1989年以每股20.88美元、高出飞虎公司股票市场价格6美元的价格收购了飞虎公司。收购之后，联邦快递拥有的着陆权从5个海外机场变成了21个国家的海外机场。虽然联邦快递也因收购背负大量债务，但是收购让联邦快递打开了新世界的大门，再也不用因为没有着陆权而把许多国家的业务转交给其他航空公司，可以直接用自己的航线自由运输。可以说，联邦快递已经找到了打开世界市场的金钥匙。
联邦快递的全球化拓展，其实中国很早就感受到了。1984年，改革开放不久后的中国就迎来了年轻的联邦快递。1988年，联邦快递公司已经向世界90个国家和地区提供隔夜快递服务，但是在较早涉足的中国市场，由于政策原因，1995年之前的联邦快递公司在中国市场不能独自运营，只能通过代理商开展快递业务。在如此条件限制下，联邦快递还是以上海为据点，开始了中国市场的开辟。当时，上海办事处只有3个工作人员，主要通过代理商利用商务航班为中国市场提供服务。1995年，随着政策的放开，联邦快递收购了常青国际航空公司。在当时的中国，常青国际航空是唯一有定期航班往返上海和美国的货运航空公司。这一收购体现了联邦快递敏锐的市场嗅觉，使联邦快递成为第一家由美国直飞中国的国际快递物流公司。