In this master’s thesis, we study Lévy processes, subordinators and their applications in random combinatorial structures. In the first chapter we introduce formal definition of Lévy processes and infinitely divisible distributions that are related to them. Characteristic functions are widely implemented in this thesis. Therefore, we state basic theorem about the characteristic exponent of infinitely divisible distribution. Three most important examples of Lévy processes are given: Poisson point process, compound Poisson process and Brownian motion. Lévy-Itô decomposition is the essential topic of second chapter. We prove that theorem using construction that involves Poisson random measures and integration of non-random functions with respect to Poisson random measure. In third chapter we investigate non-decreasing Lévy processes, subordinators. Introducing potential measures and renewal measures, we examine the connection between subordinators and renewal processes and we prove the asymptotic behaviour of relative overshoot and undershoot. Random composition and partition structures represent key concepts of the concluding chapter. Subordinator theory is used to construct regenerative composition structures.