With the popularity of Web Services and Service-Oriented Architecture (SOA), quality assurance of SOA applications, such as testing, has become a research focus. Programs implemented by the Business Process Execution Language for Web Services (WS-BPEL), which can be used to compose partner Web Services into composite Web Services, are one popular kind of SOA applications. The unique features of WS-BPEL programs bring new challenges into testing. A test case for testing a WS-BPEL program is a sequence of messages that can be received by the WS-BPEL program under test. Previous research has not studied the challenges of message-sequence generation induced by unique features of WS-BPEL as a new language. In this paper, we present a novel methodology to generate effective message sequences for testing WS-BPEL programs. To capture the order relationship in a message sequence and the constraints on correlated messages imposed by WS-BPEL's routing mechanism, we model the WS-BPEL program under test as a message-sequence graph (MSG), and generate message sequences based on MSG. We performed experiments for our method and two other techniques with six WS-BPEL programs. The results show that the message sequences generated by using our method can effectively expose faults in the WS-BPEL programs.