On April 15, 1799, the Navy Department recalled the "United States," the "Constitution" and the "Washington," "with all possible expedition." The other vessels were left in command of Captain Truxtun. Barry, in the "United States," arrived at New Castle, Delaware, May 9, 1799, and within a month at the opera it was sung that "the gallant Barry" was "by all Columbia's sons adored." He was then in Philadelphia after leaving Lieutenant Charles Stewart in charge of the frigate. Barry was, on 13th May, directed to discharge the crew whose time expired that or next month, so as to give them "an opportunity of spending their money," that they might the sooner re-enlist for another year. Officers were directed "to open rendezvous for recruiting a crew." In the meantime Captain Truxtun had arrived at Norfolk and was received with "every mark of respect and attention." Captain James Barron was there also, but on June 2d Barry requested his return to Philadelphia as necessity obliged his presence, as the President had directed the Secretary of the Navy to send "us as soon as possible to protect our defenceless coast." Lieutenant Stewart, almost daily, sent reports of the overhauling work going on preparing the frigate for a voyage. The French privateers were active along the coast harassing the merchantmen, and so audacious as even to enter our harbors. This made "the public mind very uneasy." So on June 29th the frigate sailed under orders to cruise along the coast to Charleston and after remaining there "long enough to let the citizens know" he was "in the vicinity"; he was to "proceed further south, indeed as far as the River St. Mary's," if he could return to Hampton Roads by the middle of July, where the "Constitution," Captain Talbot, would join the "United States," as it was intended to send both to the coasts of France and Spain. This did not come to be, however, as it was found necessary to have the vessels in the West Indies as soon as they could operate there. Barry received "the President's command" that "taking the 'Constitution' with you, you proceed on a cruise to the Western Isles, to Madeira and Teneriffe and thence returning by Cayenne, Surinam and the Windward Islands, and reaching Guadeloupe about the middle of October where further orders would be handed" him. Then both frigates were to proceed to San Domingo and enter the port of Cape Francois, so they might be seen by General Touissant with whom and the people he was to "endeavor to cultivate a good understanding." After remaining two or three days there he was to return to New York, leaving Captain Talbot in the "Constitution" at San Domingo to take command of that station. Barry was given leave, however, if time did not permit his going to Madeira and Teneriffe as well as the Western Isles, he might proceed no further than the Western Isles.