Stoliar was born the son of Jacob Stoliar in Chișinău, Bessarabia, which at the time was part of Romania. The Stoliars lived in Chișinău until 1927, when David and his parents moved to France to join one of Jacob's brothers, a hotelier in Vence in Provence. In 1932 the Stoliars returned to Romania, where Jacob took a job with another of David's uncles, who ran a textile factory. In 1932 David's parents divorced and his mother returned to France, settling with her brother in Paris. She took David with her to Paris but Jacob remained in Bucharest. David was at school at a boarding collège in Fontainebleau until 1936, when Jacob had him return to Bucharest. David's mother remained in France, where she remarried. David went to school at a Liceu in Bucharest, spending his summer holidays with his mother in Paris. In 1940 the Liceu expelled David for being Jewish, after which he briefly attended a Liceu set up by Bucharest Jewish community. By the end of 1940 the Romanian authorities deported David to a forced labour camp at Poligon near Bucharest.
''Struma'' voyage and disaster
In 1941 Jacob bought David a ticket to travel on the Struma, an elderly motor schooner that was bound for Palestine. Jacob got him released from the labour camp and bribed Romanian officials to issue Stoliar a passport. On 12 December 1941 David sailed from Constanța aboard the Struma, but her engine repeatedly failed and three days later a Turkish tug towed her into Istanbul. At the UK's behest, Turkey held Struma at anchor in Istanbul without allowing her passengers to disembark. Negotiations between Turkey and Britain over the fate of the refugees seemed to reach an impasse, and on 23 February 1942 Turkish authorities boarded Struma, towed her back into the Black Sea with her engine still inoperable and cast her adrift. The next morning, Soviet submarineShch-213 commanded by D.M. Denezhko sank Struma with a single torpedo. Stoliar survived the blast and clung to a floating piece of deck, and later was joined by the ship's First Officer, who was Bulgarian. Stoliar later claimed the officer told him that he saw the torpedo before it sank the Struma. The officer died overnight. After his rescue Stoliar was detained in Turkey for six weeks. After an outcry and strike in Palestine, Turkish authorities released him to Simon Brod. Afterwards British authorities acquiesced and issued him travel papers and a visa to Palestine; Brod put him on the train to Palestine. British authorities in Palestine interviewed Stoliar about the Struma sinking. He later joined the British Army, in which he served in the 8th Army in North Africa.