Movement primitives are a well established approach for encoding and executing robot movements. While the primitives themselves have been extensively researched, the concept of movement primitive libraries has not received as much attention. Libraries of movement primitives represent the skill set of an agent and can be queried and sequenced in order to solve specific tasks. The goal of this work is to segment unlabeled demonstrations into an optimal set of skills. Our novel approach segments the demonstrations while learning a probabilistic representation of movement primitives. The method differs from current approaches by taking advantage of the often neglected, mutual dependencies between the segments contained in the demonstrations and the primitives to be encoded. Therefore, improving the combined quality of both segmentation and skill learning. Furthermore, our method allows incorporating domain specific insights using heuristics, which are subsequently evaluated and assessed through probabilistic inference methods. We demonstrate our method on a real robot application, where the robot segments demonstrations of a chair assembly task into a skill library. The library is subsequently used to assemble the chair in an order not present in the demonstrations.