The increasing rate of e-commerce orders necessitates a faster packaging process, challenging warehouse employees to correctly choose the size of the package needed to pack each order. To speed up the packing process in the Austrian e-commerce company niceshops GmbH, we propose a machine learning approach that uses historical data from past deliveries to predict suitable package sizes for new orders. Although for most products no information regarding the volume is available, using an approximate volume computed from the chosen packages of previous orders can be shown to significantly increase the performance of a random forest algorithm. The respective learned model has been implemented into the e-commerce company’s software to make it easier for human employees to choose the correct packaging size, making it quicker and easier to fulfill orders.