Motivated by applications in cloud computing, this paper studies a hybrid problem that combines the Parallel Two-stage Flowshop Scheduling problem with the Bin Packing problem, referred to as the Two-stage Bin Packing problem. Given a sequence of two-stage jobs, the problem aims to pack them into the minimum number of two-stage flowshops such that the completion time of each flowshop does not exceed a given time limit. To our best knowledge, the problem has not been studied before. Recognizing its NP-hardness, we investigate several approximation algorithms. First, we present two online algorithms based on the well-known First-fit and Next-fit strategies, which achieve an absolute approximation ratio 4 with a lower bound 3.166 and a tight asymptotic approximation ratio 4, respectively. We then introduce an algorithm that applies Johnson’s Order to each individual flowshop and assigns incoming jobs to flowshops using the First-fit strategy, which is shown to have an asymptotic approximation ratio 3.061 with a lower bound 2.66. Besides, we show that applying Johnson’s Order in flowshops cannot improve the Next-fit strategy in terms of approximation ratio.