Despite the many benefits of pulses, their consumption is still very low in many Western countries. One approach to solving this issue is to develop attractive pulse-based foods, e.g., plant-based cheeses. This study aimed to assess the suitability of different types of pulse flour, from boiled and roasted yellow peas and faba beans, to develop plant-based cheese analogues. Different stabilizer combinations (kappa- and iota-carrageenan, kappa-carrageenan, and xanthan gum) were tested. The results showed that firm and sliceable pulse-based cheese analogues could be prepared using all types of pulse flour using a flour-to-water ratio of 1:4 with the addition of 1% (w/w) kappa-carrageenan. The hardness levels of the developed pulse-based cheese analogues were higher (1883–2903 g, p < 0.01) than the reference Gouda cheese (1636 g) but lower than the commercial vegan cheese analogue (5787 g, p < 0.01). Furthermore, the crude protein (4–6% wb) and total dietary fiber (6–8% wb) contents in the developed pulse-based cheese analogues were significantly (p < 0.01) higher than in the commercial vegan cheese analogue, whereas the fat contents were lower. In conclusion, flours from boiled and roasted yellow peas and faba beans have been shown to be suitable as raw materials for developing cheese analogues with nutritional benefits.