Interest in Cuffe's request now shifts to the Senate where a measure was passed authorizing the President of the United States to permit Paul Cuffe to depart from the United States with a vessel and cargo for Africa and similarly to return. The House was informed of this action on the twenty-seventh of January and four days later read the Senate bill twice and referred it to the Committee on Commerce and Manufacturing. This committee reported that since the government had been compelled to prohibit the coasting trade, it would be impolitic to relax the provisions on the "application of an individual, for a purpose, which, how benevolently soever conceived, cannot be considered in any other light than as speculative—the efforts heretofore made and directed by the zeal and intelligence of the Sierra Leone Company having failed to accomplish the object designed by its institution."[36]

This report was referred to the Committee of the Whole House and debated on the nineteenth of March. The representatives who wished to grant Cuffe's request agreed that the Senate bill would be an invitation to free blacks to emigrate to Africa. This part of the population they said could well be spared. The opponents of Cuffe's request doubted the expediency of permitting to go out a cargo which must necessarily sail under British license. Such a license would be granted, they argued, only if advantageous to the enemy. The House by a vote of 72 to 65 rejected the Senate measure and Cuffe's request was denied.

He fared little better at the hands of the British Government. Allen carried the request to the ministers and told them that it was the opinion of many that the one thing most needed to help Sierra Leone was to enlist the services of Paul Cuffe. If the Government granted the license, it was hoped that a vessel could be purchased, that Cuffe be made its proprietor, and that it be used to carry African produce to Britain. The ministers, from the Chancellor of the Exchequer on down, were exceedingly kind and were willing to grant the license but could not, owing to the navigation laws, insure the vessel against a seizing officer. Such an officer might consider the boat more valuable than his office. Allen thought such a risk too great either for Cuffe or the African Institution and the request for a license was withdrawn.

Cuffe's spirit would not down. Let Congress turn him down and the British ministers deny his request. There was still one group willing to help him along. This group was the Society of Friends at Westport. Here was fuel for the fire of Cuffe's zeal. Ebenezer Baker, clerk of the monthly meeting, on the "16th of the 11th month 1815" records:

Our friend Paul Cuffe (who is a member of our religious society) informed this meeting that he has a prospect of making a voyage to Africa on business, and in a particular manner, with the laudable view of endeavoring to promote the temporal and civil improvement and comfort of the inhabitants of some parts of that country; which having had our solid deliberation, we feel desirous that he may be enabled to accomplish this object, to the peace of his own mind; and leave him at liberty to pursue his prospect, recommending him to the friendly notice and regard of those amongst whom his lot may be cast.[37]

Just as soon as the war was over Cuffe set sail for Africa. The papers evidently were well supplied with his plans, for a Louisville paper, The Western Courier, related that "Capt. Paul Cuffe, a man of color is about to proceed to Africa, with several families to form a settlement there. He will sail in the brig Traveller, now at Philadelphia, receiving two families there, afterwards touch at New Bedford and receive the remainder of her company, and then proceed the latter part of October on her voyage."

The Traveller cleared from the custom house on the second of December. Two days later Cuffe wrote Allen, "I shall sail through God's permission the first wind after tomorrow." The first wind came the tenth of December. When the Traveller finally sailed she carried a cargo of tobacco and soap, candles, naval stores and flour. She had also iron with which to build a sawmill, a wagon, grindstones, nails and glass, and a plow. There were thirty-eight passengers, eighteen heads of families and twenty children.

The Captain himself reported the voyage to the American Colonization Society in this laconic letter:

Thirty-eight in number went out with me, their expenses were estimated at one hundred dollars per head, but were there a large number they could be carried out for sixty dollars. The expense of thirty of the above number was born by Paul Cuffe. The others paid for their own passages. In addition to the above expense, I furnished them provisions to the amount of 150 pounds 8s 3d sterling; all this was done without fee or reward—my hope is in a coming day.[38]

The passengers were all common laborers and they wished to cultivate the land. Perry Locke, a Methodist, was licensed to preach. He is an honest man, wrote Cuffe, but "has rather a hard voice for a preacher." Another passenger was Antony Survance, a native of Senegal, who had been sold to the French in St. Domingo. During the revolution he came to Philadelphia. He had learned to read and write and had studied navigation, but Cuffe thought he would never make a mariner on account of seasickness. He paid his passage to Africa and hoped by and by to return to Senegal. He said the black man had two eyes and two ears, the white man has no more. Could he not hear with his ears and see with his eyes. All the passengers were provided with certificates of good character.[39]