Combinatorics has constantly evolved from the mere counting of classes of objects to the study of their underlying algebraic or analytic properties, such as symmetries or deformations. This was fostered by interactions within particular statistical physics, where the objects in the class form a statistical ensemble, where each element comes with some probability. Integrable systems form a special subclass: that of systems with sufficiently many symmetries to be amenable to exact solutions. In this talk, we explore various basic combinatorial problems involving discrete random surfaces, dimer models of cluster algebra, or two- dimensional vertex models, whose (discrete or continuum) integrability manifests itself in different manners: commuting operators, conservation laws, solitons, flat connections, quantum Yang-Baxter equation, etc. All lead to often simple and beautiful exact solutions.