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 under-explored, 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 systems 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.