n early July 1993, two Middle Eastern men arrived in the bustling port of Limassol, Cyprus, and presented themselves as representatives of the bin Laden group of companies.

Back then, the name was more closely associated with the powerful construction conglomerate, the Saudi Binladin Group, and a lawyer and a local accounting firm helped the men set up two companies that were used to purchase a rusty 224-foot freighter.

But one of the Lebanese men was Wadih El-Hage, an operative in the other bin Laden group, the terrorist network Al Qaeda that was then in its formative stages. For the next few years, the ship, Seastar, worked the waters of the Red Sea carrying sesame and watermelon seeds and, some investigators suspect, cargo far more threatening.

Al Qaeda is now said to control at least 20 ships, and American officials have been concerned that Osama bin Laden might use them to escape Afghanistan.

The tale of the tramp freighter Seastar evokes a different period in the life of Al Qaeda, when Mr. bin Laden began mixing commerce with terror and neither he nor his chief lieutenants were recognized for what they were to become.

At the time, the 27-year-old gray and white vessel attracted little attention from terrorism investigators. Nor was there much of a stir 18 months ago when the ship, then owned by a company in Norway that American officials suspect was connected to Al Qaeda, sank off the coast of Oman.

But in the months before Sept. 11, European and American investigators began to review the deal for the ship, which cost $450,000 and was then one of the largest known cash purchases made by companies under the control of Mr. bin Laden.

Investigators have found no evidence linking the ship to any terror attack, although there is one notable coincidence: Records show that the ship left Jidda, Saudi Arabia, in November 1995, one day before a car bomb exploded hundreds of miles away in Riyadh, the capital, killing five Americans and two others. Mr. bin Laden publicly praised the attack.

"Our view," said one United States government official, "was that it was mostly involved in carrying legitimate cargo."

Even so, the ship is now seen as emblematic of Al Qaeda's strategy. "Everything these people did had a goal, and that goal was terrorism, whether it was operational or to sustain the organization," said one American official who has tracked Al Qaeda operatives around the world. "You don't buy a half-million-dollar ship for nothing."

Government prosecutors have shown in court that Mr. bin Laden used a far-reaching network of legitimate businesses, including construction and farming companies and an investment firm, to generate money to support terrorism. They have also said that Mr. bin Laden used a labyrinthine network of front companies to conceal his terrorist operations.

Mr. El-Hage, who helped arrange the purchase of the ship through Cyprus, worked for years to build that commercial edifice. A naturalized American citizen from Lebanon, Mr. El-Hage was Mr. bin Laden's personal secretary in Sudan in the early 1990's and traveled widely on his behalf, making purchases and setting up front companies.

In 1992, for example, Mr. El-Hage acted on Mr. bin Laden's behalf to buy a decommissioned American military passenger jet for about $200,000, court testimony shows. Mr. El-Hage said Mr. bin Laden wanted the plane to transport Stinger antiaircraft missiles from Pakistan to Sudan and to carry produce, a witness said.

Mr. El-Hage's business activities were cited by prosecutors earlier this year in the trial stemming from the 1998 bombings of two American embassies in East Africa. "The evidence shows that Wadih El-Hage led a double life," a federal prosecutor told the jury, "a secret criminal life on behalf of Al Qaeda, and that he performed logistical services for Al Qaeda to make sure that others in Al Qaeda could carry out their deadly acts."

Mr. El-Hage was convicted of terrorism conspiracy and sentenced to life in prison.

At the trial, Mr. El-Hage's lawyers, Sam A. Schmidt and Joshua L. Dratel, contended that Mr. El-Hage worked for Mr. bin Laden's legitimate businesses and had nothing to do with terrorism. Although Mr. Schmidt said this month that he was unaware of the ship deal, he said the purchase of a ship to move products from Sudan would have been "absolutely consistent with his role in the Laden enterprises."

"That was his job," Mr. Schmidt said, "to travel to buy things for the business."

Court testimony from the case suggests that Mr. bin Laden kept close tabs on his business operations, and big-ticket deals were not undertaken without his approval. A notebook kept by Mr. El-Hage, which was introduced in the trial, suggests that Mr. El-Hage was working on a ship deal as early as 1993.

In the notebook, he dutifully recorded his plans and thoughts about the deal. Under the scribbled heading, "Ship owning comp," he outlined what he needed to create such a company.

He wrote: "1. Names for the company. 2. Shareholders names addresses." Under "directors," he listed himself and an associate, Sadek Walid Awaad. He also wrote notes about the cargo capacity and engine size of the ship he had in mind.

Mr. El-Hage is at the hub of an array of men whom investigators have linked to Al Qaeda.

Mr. Awaad, who accompanied Mr. El-Hage to Cyprus, was identified in court testimony as having worked for businesses owned by Mr. bin Laden.

In Cyprus, the lawyer who helped Mr. El-Hage and Mr. Awaad said he was told to send all legal papers to an address in Hamburg, Germany, which appears on Mr. El-Hage's business card and also has been used by Mr. Awaad in corporate records.

The address, Uhlenhorster Weg 34, belongs to Mamoun Darkazanli, who German investigators suspect was part of a Qaeda cell in Hamburg that supported the Sept. 11 attacks. After the attacks, the Bush administration froze his assets, accusing him of providing financial assistance to terrorists, an accusation he has denied. Mr. Darkazanli, reached recently in Hamburg, declined to comment, citing the advice of his lawyer.

Arno Heiden, an employee of the broker that handled the 1994 sale, Walther M?ler G.M.B.H. & Company, called the deal "all perfectly above board." He said Mr. Darkazanli was involved in the transaction, but he would not elaborate. He said in an interview that F.B.I. agents and German police came to the broker's office last March and photocopied documents pertaining to the sale.

When Mr. El-Hage was setting up companies to buy a ship, his notes suggest, he wanted to use as a bank reference a man named Sidi Tayyib, a senior aide to Mr. bin Laden. Mr. Tayyib had married a niece of Mr. bin Laden's and oversaw the day-to- day operations of his business empire, testimony shows.

At the direction of Mr. El-Hage and later Mr. Awaad, two companies were set up in Cyprus, according to the lawyer there, who asked that he not be named. He said the formation of the companies seemed completely routine.

By April 1994, a deal was arranged to buy the ship, then called the Jennifer, which was being sold by a German sea captain named Claus Darley, according to records and interviews.

Captain Darley is at sea until June and unavailable for comment, according to his wife, Sabine. She described the Jennifer as "a rusty little freighter." She said she and her husband never met the buyers and knew little about them except that "they were Arabs."

The freighter was in such bad condition, the Cyprus lawyer said, that it did not meet Cyprus's seaworthiness standards. So a third company was created in Malta, where the standards are less restrictive, he said.

After the sale, the freighter underwent repairs in Limassol, with Mr. Awaad living aboard and walking around town affecting a nautical air, the lawyer recalled. "He had no idea how ships worked or what they were," the lawyer said.

Over the next two years, the freighter visited dozens of Red Sea ports, according to shipping records from Lloyd's Marine Intelligence Unit in London. In the 11 months ending January 1996, the ship made 16 voyages from Port Sudan to Jidda, in many cases carrying 500-ton cargoes of sesame and watermelon seeds, according to Barwill Agencies in Sudan, which was hired to load and unload the cargoes. The ship also carried cement between Port Sudan and Aqaba, Jordan, the firm said.

Only its November 1995 trip to Jidda showed a possible overlap with terrorism, and even that is speculative. After spending more than two weeks in Jidda, the Seastar sailed for Port Sudan on Nov. 12. The next day a car bomb in Riyadh killed seven people, including five American government employees. Although American authorities have never charged anyone in connection with the attack, Mr. bin Laden later commended the bombing as "praiseworthy terrorism."

In 1996, the ship was sold to a Norwegian company controlled by a group of Somalis. A United States official speaking on the condition of anonymity said this month that the company was "suspected of having ties to Al Qaeda," but declined to provide details. No evidence of any links could be found.

In May 2000, the ship, by then 34 years old and renamed Sky 1, chugged out of Dubai, a busy Persian Gulf port. Bound for Somalia, with a full load of timber, steel and cars, the ship steamed through the placid waters of the Strait of Hormuz, and southwest through the Arabian Sea.

It never reached its destination. The Sky 1 began to list heavily off the coast of Oman and sank less than two days later. The crew was rescued by a Russian freighter that responded to a distress call. The Russian captain, Aleksandr Filipov, said he then sailed on, bound for Yemen, leaving the Sky 1 behind, deserted, drifting and sinking.

More recently, Omani authorities, saying they were concerned the wreckage could pose a hazard to navigation, asked the British Royal Navy to find the wreck, a Navy spokesman in London said.

The Bulldog, a British ship that uses sophisticated undersea sensors to survey the ocean floor, was sent to help search for the Sky 1's wreckage, the spokesman said, but no trace of the vessel has been found.