With the rapid progress in quantum hardware, there has been an increased interest in new quantum algorithms to describe complex many-body systems searching for the still-elusive goal of “useful quantum advantage.” Surprisingly, quantum algorithms for the treatment of open quantum systems (OQSs) have remained underexplored, in part due to the inherent challenges of mapping non-unitary evolution into the framework of unitary gates. Evolving an open system unitarily necessitates dilation into a new effective system to incorporate critical environmental degrees of freedom. In this context, we present and validate a new quantum algorithm to treat non-Markovian dynamics in OQSs built on the ensemble of Lindblad's trajectories approach, invoking the Sz.-Nagy dilation theorem. Here we demonstrate our algorithm on the Jaynes-Cummings model in the strong-coupling and detuned regimes, relevant in quantum optics and driven quantum system studies. This algorithm, a key step towards generalized modeling of non-Markovian dynamics on a noisy-quantum device, captures a broad class of dynamics and opens up a new direction in OQS problems.