Boil-off gas (BOG) generation in liquefied natural gas (LNG) regasification terminals is substantial and unavoidable. Most terminals employ a cost-intensive BOG reliquefaction process using the send-out LNG. In this work, we study the preliminary design of this process with the objective of minimizing its total annualized cost (TAC). We present a comprehensive superstructure for the reliquefaction process that incorporates several process options for cooling BOG using LNG at different pressures, and allows recondensation in multiple stages. Then, we develop custom simulation/sizing modules for the process units in our superstructure, and implement a procedure to reduce explicit constraints during optimization. Considering realistic design specifications and operational constraints, we optimize a case study terminal for various BOG rates and conditions. While the TAC increases substantially with BOG rate, two-stage recondensation is always optimal. A 2-recondenser scheme with BOG cooling by the high-pressure LNG before the first recondenser is optimal for most cases. (C) 2018 Elsevier Ltd. All rights reserved.