联邦快递公司一开始向25个城市提供服务，但令人失望的是，第一天夜里运送的包裹只有186件。在开始营业的26个月里，联邦快递公司亏损2930万美元，欠债主4900万美元，联邦快递处在随时都可能破产的险境，公司的早期支持者打起了退堂鼓，不肯继续投资。这是联邦快递公司最为艰难的时期，在企业初创最艰难的时期，史密斯以他不屈不挠的精神、以对前途的无限信心和十足的勇气，以他超凡的领导者的魅力，吸引了联邦公司的雇员，使他们心甘情愿地把自己的利益和前途交给公司，同弗雷德·史密斯一起同舟共济渡过难关。

    为了抵偿公司的债务，他卖掉了自己的私人飞机，甚至，他居然伪造律师签字，从家庭信托基金中提取本属于他两个姐姐的钱。为了改善经营情况，弗雷德·史密斯竭尽全力争取客户，开拓市场，为得到美国行政总局的合约，联邦快递公司在西部开辟了6条航线，在与其他企业的竞争中，他把价格杀得很低，以至使人怀疑是否还有利润。而弗雷德·史密斯却着眼于更长久的利益，他认为尽管这笔业务并没有很高的利润，却可以用来充当公司的门面，公司可以借这笔业务向外界表示：“看啊，连邮政总局的合约都能拿到手，对联邦快递公司的服务还有什么不放心的。这样做不仅让投资者放心，还可以争取更多的用户。”

    “天道酬勤”，在困境中拼搏的联邦快递公司遇到了意外的好运气，首先是政府解除了对航空运输业的限制，极大地增加了货运行业的运输量。由于对商业运输的需求突然猛增，国内主要货运机构对大城市的业务都应接不暇，根本就没有力量去满足小城市的要求，这就为联邦快递提供了重大的市场缺口，使它的业务量很快增加。另外的一个好运气是，1974年，由于联合包裹运输公司的员工长期罢工，终于使铁路快运公司破产。这两件事都为联邦快递公司提供了发展公司业务、改善公司状况的好机会。

    1975年，公司的经营状况开始好转，7月份是联邦快递公司第一个盈利的月份，全公司创利5.5万美元，当年的营业收入达到了7500万美元。这时候的联邦快递公司，已经拥有3.1万个固定客户。联邦快递公司为全国各地的客户运送零件、血浆、移植器官、药品等各种需要迅速运递的物品。联邦快递公司在130个城市和75个机场提供隔夜快递服务。联邦快递公司的紫色飞机，在每天的夜晚载运着数不清的包裹在通往全国各地的航线上穿梭。1976年，联邦快递公司获纯利350万美元；1977年年度经营收入突破1亿美元，获纯利820万美元。联邦快递公司终于走出困境，并创造了奇迹。1977年，弗雷德·史密斯被纽约一家杂志评选为全国十大杰出企业家，并称赞“在短短的5年内，他那创新的行销体系以及成功的公众形象宣传使他一下子由一无所有变为营业额1.1亿美元、净利润820万美元的大企业家。”1978年8月，《骑士报》发表文章指出：“在艰难中仍然屹立不动摇，凭借不屈不挠的意志与战斗力去抵抗阻挡在前进道路上的任何横逆，他卓绝的表现不仅是企业家的楷模，更是我们每一个人都应当效法的。”给史密斯投资的风险投资家们看中的就是他的这种不屈不挠的精神。

    公司股票挂牌上市，联邦快递公司跃居全世界航空货运公司之首。占有股份的风险投资家们已经开始计算自己的收益了，而利润在不断的变化，因为股票在不断的增值。

    随着联邦快递公司业务的迅速发展和快递服务市场的不断扩大，公司原有的达索尔特鹰式小型飞机已经明显不能适应隔夜快递业务的需要。根据1938年通过的《联邦航空法》，美国的航空运输业由美国联邦政府牢牢控制。《联邦航空法》规定，只有载重量不高于7500磅的小型飞机运送货物才不必向联邦政府申请许可证。当初制定这项法规主要是为了保护客运航空公司，而这项规定却严重地阻碍了联邦快递公司的发展。为了避开《联邦航空法》的限制，联邦快递公司在成立之初只购买了不用申请许可证的达索尔特鹰式小型飞机。随着公司快递业务的不断增加，联邦快递公司为了保证业务量较大航线的需要，有时不得不用8架达索尔特鹰式小型飞机并排飞行，如果改用一架较大的飞机代替这8架小型飞机，不但省事而且也省钱。于是，弗雷德·史密斯向联邦民用航空委员会提出申请5架DC-9型飞机从事隔夜快递服务的许可证，他的申请遭到了拒绝。于是弗雷德·史密斯便决定为废除已经过时的《联邦航空法》而斗争。他在华盛顿国会议员中间游说，领导了一场为时18个月的游说议员的运动，并向国会正式递交了“联邦快递法案”。最后这个法案由于竞争对手卡车司机联合会、尼航运输协会和飞虎运输公司的强烈反对而没有通过。但是到了1977年，吉米·卡特当选为新一届美国总统，他公开表示赞同解除对航空公司和航空货运公司的管制。这样一来，联邦快递公司如愿以偿，决定购买一批载重量达4.2万磅的波音727型飞机。

    公司的进一步发展以及购买波音727型飞机等等均需要较大的资金，公司需要筹集到更多的资金。弗雷德·史密斯决定，让联邦公司的股票公开上市，面向社会融资。1978年4月，联邦快递公司在纽约证券交易所正式排牌，公开出售第一批股票。联邦快递公司股票的发行，不仅筹集到了购买飞机的巨资，而且使公司的早期投资者得到了回报。这一年年底，弗雷德·史密斯收购了他两个姐姐在公司的全部股权，使她们得到了可观的收入，补偿了她们的损失。